该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定两个长度为 $N$ 的小写英文字符串 $S$ 和 $T$，以及 $M$ 对整数：

$(L_1,R_1),(L_2,R_2),…,(L_M,R_M)$

按顺序对每个 $i=1,2,…,M$ 执行以下操作：

• 交换 $S$ 中第 $L_i$ 个到第 $R_i$ 个字符与 $T$ 中第 $L_i$ 个到第 $R_i$ 个字符。 例如，若 $S$ 为 $hellochina$，$T$ 为 $helloworld$，且 $(L_i,R_i)=(3,5)$，则交换后 $S$ 变为 $helloworld$，$T$ 变为 $hellochina$。

执行完所有 $M$ 次操作后，输出字符串 $S$。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ 。

每个测试用例的第一行包含整数 $N$ 和 $M$ 分别表示字符串 $S$，$T$ 的长度和整数对的数量。

每个测试用例的第二行包含字符串 $S$ 。

每个测试用例的第三行包含字符串 $T$ 。

每个测试用例的接下来 $M$ 行，每行包含两个整数 $L_i$ $R_i$表示整数对 $(L_i，R_i)$字符串。

限制：

$（1≤t≤1000）$

$（1 ≤ L_i ≤ R_i ≤ N）$。

$（1 ≤ N ≤ 5×10^5，1 ≤ M ≤ 2×10^5）$；

保证每个测试 $N$ 的总和不超过 $5×10^5$，$M$ 的总和不超过 $2×10^5$

输出格式

对于每个测试用例，输出一个字符串 $S$，即执行完所有 $M$ 次操作后的字符串 $S$ 。

样例

2
5 3
apple
lemon
2 4
1 5
5 5
10 5
lemwrbogje
omsjbfggme
5 8
4 8
1 3
6 6
1 4

lpple
lemwrfogje

样例解释

对于第一组样例：

初始时，$S$ 为 $apple$，$T$ 为 $lemon$。

在执行 $i = 1$ 的操作后， $S$ 变为 $aemoe$，$T$ 变为 $lppln$。

在执行 $i = 2$ 的操作后， $S$ 变为 $lppln$，$T$ 变为 $aemoe$。

在执行 $i = 3$ 的操作后， $S$ 变为 $lpple$，$T$ 变为 $aemon$。

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