题目描述

训练营晚会要布置一面发光墙，墙上有上下两条长度相同的灯带。

每个位置上，上灯带和下灯带各有一个小灯片，灯片上印着一个小写字母。为了调试效果，老师会连续发出 Q 条指令。

每条指令给出一个区间 [L, R]。执行这条指令时，需要把区间内每一个位置的上下两个灯片交换：

• 位置 L 的上下灯片交换；
• 位置 L+1 的上下灯片交换；
• ...
• 一直到位置 R 的上下灯片交换。

所有位置的编号从 0 开始。

请你输出所有指令执行完之后，上下两条灯带最终显示的字符串。

输入格式

第一行输入一个仅由小写字母组成的字符串 S1，表示上灯带一开始的内容。

第二行输入一个仅由小写字母组成的字符串 S2，表示下灯带一开始的内容。

第三行输入一个整数 Q，表示指令数量。

接下来 Q 行，每行输入两个整数 L 和 R，表示本次要交换的区间。

输出格式

输出两行。

第一行输出最终的上灯带字符串。

第二行输出最终的下灯带字符串。

样例 1

abcdefghijkl
kedadadadada
2
0 3
5 7

kedaeadaijkl
abcddfghdada

样例 1 说明

第一次交换区间 [0,3]，前四个位置的上下灯片互换。

第二次交换区间 [5,7]，第 5 到第 7 个位置的上下灯片互换。

两次操作完成后，上灯带为 kedaeadaijkl，下灯带为 abcddfghdada。

样例 2

abcde
vwxyz
10
0 0
0 2
1 3
2 4
0 0
1 1
2 2
3 3
4 4
0 4

abxdz
vwcye

数据范围

对于 30% 的数据：

• 1 <= |S1|, |S2| <= 100
• 1 <= Q <= 100
• |S1| = |S2|
• 0 <= L <= R < |S1|

对于 100% 的数据：

• 1 <= |S1|, |S2| <= 500000
• 1 <= Q <= 200000
• |S1| = |S2|
• 0 <= L <= R < |S1|