AT_abc419_d.[ABC419D] Substr Swap

给定长度为 $N$ 的小写英文字母字符串 $S$ 和 $T$，以及 $M$ 对整数 $(L_1,R_1),(L_2,R_2),\ldots,(L_M,R_M)$。

请依次对 $i=1,2,\ldots,M$ 执行以下操作：

• 交换 $S$ 的第 $L_i$ 到第 $R_i$ 个字符与 $T$ 的第 $L_i$ 到第 $R_i$ 个字符。
  • 例如，如果 $S$ 为 abcdef，$T$ 为 ghijkl，且 $(L_i,R_i)=(3,5)$，则 $S$ 和 $T$ 变为 abijkf 和 ghcdel。

请输出经过 $M$ 次操作后的字符串 $S$。

输入按以下格式从标准输入读入：

$N$ $M$
$S$
$T$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_M$ $R_M$

输出经过 $M$ 次操作后的字符串 $S$。

样例解释 1

初始时，$S$ 和 $T$ 分别为 apple 和 lemon。

• 第 $i=1$ 次操作后，$S$ 和 $T$ 分别变为 aemoe 和 lppln。
• 第 $i=2$ 次操作后，$S$ 和 $T$ 分别变为 lppln 和 aemoe。
• 第 $i=3$ 次操作后，$S$ 和 $T$ 分别变为 lpple 和 aemon。

因此，经过三次操作后的字符串 $S$ 为 lpple。

数据范围

• $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$ 均为整数。

由 ChatGPT 4.1 翻译