STAVATAR - The Last String Bender

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 simultaneously.

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 successfully robbed the records (scrolls) of these modifications to the passwords. But he is 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. 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 (of course). the printable characters can represented as
the printable characters representation.

Example

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

Output:
ahcdkl
gbijef

Note: To be precise the representation of output is "ahcdkl\ngbijef\n".

My Best: C++: 0.35s, python2.7: 12.57, pypy: 6.27.


Added by:eightnoteight
Date:2015-04-03
Time limit:0.5s-2.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY

hide comments
2015-04-16 18:41:37 Shaka Shadows
Funny problem, quite similar to this one: http://www.spoj.com/problems/SAMTWARR/, and yes, solvable by applying a small trick to the "obvious" brute force solution. This one is even good for software engineering algorithmic interviews. Thanks @eightnoteight, nice one!!!

Last edit: 2015-04-16 21:07:01
2015-04-13 14:37:05 kelaseek
how to input \r and whitespaces and all. pls reply

re(eightnoteight):
as they are also characters you can simply read single character at a time....


Last edit: 2015-04-13 16:20:39
2015-04-12 02:00:17 gamer496
note carefully the black box string can contain whitespace characters except newline character

Last edit: 2015-04-12 19:54:09
2015-04-10 17:00:39 eightnoteight
@darol, it is backtick indeed.

Last edit: 2015-04-10 17:01:01
2015-04-07 00:52:01 darol
is backtick character in input 1 char long? should output backtick char or & #124?

Last edit: 2015-04-07 00:55:51
2015-04-06 12:08:35 Vipul Srivastava
ok Thanks @eightnoteight
2015-04-04 23:40:52 adamant
del pls

Last edit: 2015-04-05 00:05:45
2015-04-04 14:34:18 eightnoteight
hey @devilwolverine
I am extremely sorry! I deleted your comment accidentally. actually your algo is too slow O(n^2) as n, m, Li, Ri can be as high as 10^6, so your solution gives TLE. and i think there's no problem regarding the python Time Limit

Last edit: 2015-04-05 03:31:14
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.