分数: 400 点
问题陈述
你的长度是-N 小写英文字符串 S 和 T,和 M 整数对 (L_1,R_1),(L_2,R_2),\ldots,(L_M,R_M).
执行以下操作 i=1,2,\ldots,M 按顺序:
- 交换 L_i-th 至 R_i第一个字符 S 和 L_i-th 至 R_i第一个字符 T.
- 例如,如果
牌匾上写着 S is
abcdef, T isghijkl,和 (L_i,R_i)=(3,5),那么 S 和 T 成为abijkf和ghcdel。
- 例如,如果
牌匾上写着 S is
查找字符串 S 执行后 M 操作。
约束
- 1\leq N\leq 5\times 10^5
- 1\leq M\leq 2\times 10^5
- 每个 S 和 T 是一个长度-N 小写英文字符串。
- 1\leq L_i\leq R_i\leq N
- N, M, L_i,和 R_i 是整数。
输入
输入由标准输入按以下格式给出:
N M S T L_1 R_1 L_2 R_2 \vdots L_M R_M
输出
输出 S 执行后 M 操作。
示例输入 1
5 3 apple lemon 2 4 1 5 5 5
示例输出 1
lpple
最初, S 和 T 是 apple 和 lemon。
- 操作后 i=1, S 和 T 是
aemoe和lppln。 - 操作后 i=2, S 和 T 是
lppln和aemoe。 - 操作后 i=3, S 和 T 是
lpple和aemon。
因此,字符串 S 三个操作之后是 lpple.
示例输入 2
10 5 lemwrbogje omsjbfggme 5 8 4 8 1 3 6 6 1 4
示例输出 2
lemwrfogje