Stan and Cartman are playing a simple game. On a table Stan has placed “N” glasses and inside each glass he has kept a piece of paper where he has written one word. On the table he has marked “N” positions as 1, 2, up to N. Stan shows Cartman the words written inside each glass. Now Stan can perform two kinds of operations, he can either ask Cartman the word written inside the glass at position “Z” or he can swap the glasses at position “X” and “Y”.

Can you help him in this task?

Input

The first line will contain two integers “N” and “Q”. Q is the number of operations Stan will perform. Each of the next “N” lines will contain one word consisting of only lowercase letters. The first word is the word written inside glass at position 1 and so on. After that Q lines follow. Each of these Q lines will be of the form “Swap X Y” or “Answer Z”. “Swap X Y” means he swaps the glasses at positions X and Y. “Answer Z” means he wants to know the word written inside the glass at position Z.

Output

For each query “Answer Z” print one word in a separate line denoting the word written inside the glass at position Z.

Constraints

1 <= N <= 10^5

1 <= Q <= 10^5

1 <= X, Y, Z <= N

1 <= Length of each word <= 20

Example

Input:
5 5
Stan
Cartman
Kenny
Kyle
Butters
Answer 3
Swap 1 3
Swap 2 3
Answer 2
Answer 1

Output:
Kenny
Stan
Kenny