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
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.
hide comments
Siddharth Singh:
2016-06-24 17:02:56
AC in 1
|
|
azam_9:
2016-06-24 10:27:17
@author-can u please check my code...i have checked each test case from spojtoolkit but thn also i m gettin WA.
|
|
HARSHIT SINHA:
2015-07-01 14:21:23
what a story!! |
|
chinmay rakshit:
2015-06-30 13:40:40
hint 1: solution is O(n)
|
|
janina:
2015-06-28 16:45:27
cool one ;) ;).........easy though.. Last edit: 2015-06-28 16:47:21 |
|
Sergio Vieri:
2015-06-14 06:25:15
Solved 0.23 sec in Assembly.. |
|
Shubham Bansal:
2015-05-30 06:28:29
take care that string may include spaces. also read the note for output format.
|
|
FoolForCS:
2015-05-29 21:48:53
A tip, cost me far too many WA's, DO NOT use inbuilt isprint() function. |
|
pingal tirkey:
2015-05-26 09:25:27
Nice problem,it took lots of TLE and WA to finally get AC :)
|
|
vipul:
2015-05-17 21:45:54
accepted in java first one Last edit: 2015-06-16 00:46:09 |
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 |