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

输入 #1

5 3
apple
lemon
2 4
1 5
5 5

输出 #1

lpple

输入输出样例 #2

输入 #2

10 5
lemwrbogje
omsjbfggme
5 8
4 8
1 3
6 6
1 4

输出 #2

lemwrfogje

说明/提示

样例解释 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$ 均为整数。