← 返回题目列表

AtCoder · abc419_d

G. 子字符串交换

中文机器翻译题面 查看原题

分数: 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 is ghijkl,和 (L_i,R_i)=(3,5),那么 S 和 T 成为 abijkf 和 ghcdel。

查找字符串 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