当前没有测试数据。

The charland nation has declared a war on all nations. To defeat the charlord stavatar has to meet his previous stavatar form(stoku) in the char temple for some guidance. To open the char temple one has to enter two passwords simulatenously.

The charland benders knew that this would happen some day and they modified the password to char temple with a special charland bending technique.

The special charland bending technique is swapping the characters between two strings(passwords) of length N from L to R in their respective positions(Inclusive).

for example a typical special charland bending technique on the below strings(L=2 and R=4)

abcdef ghijkl

transforms them to

abijkf ghcdel

now the stavatar has successfuly robbed the records(scroles) of these modifications to the passwords. but a little bit confused on how to obtain the original passwords. can you help him ??

Input

First line contains  the length of two strings(N) and then the next two lines contain the two modified passwords of length N each. and then in the next line M - the number of bendings applied to get the given passwords. the next M lines consist of two space separated integers L and R.

Output

print the two passwords in two lines.

Constraints

1 <= N <= 106
1 <= M <= 106
0 <= L <= R < N
a password can contain any printable character except a newline(ofcourse). the printable characters can represented as

Example

Input:
6
abcdef
ghijkl
4
2 4
1 3
4 4
4 5

Output:
ahcdkl
gbijef

Note: To be presice the representation of output is "ahcdkl\ngbijef\n"
My Best: C++: 0.35s, python2.7: 12.57, pypy: 6.27.