Now we have a problem here, there are $N$ stacks in front of you. they are numbered from 1 to $N$. Each of them are initially empty. Now you will have $Q$ operations. Each operation can be one the below 4 types:

push i x, Push a value of $x$ to stack numbered $i$

pop i, Pop value from the stack numbered $i$, if stack is empty discard the operation

put i j, Put the $j$-th stack on top of the $i$-th stack. So there will be no element left on the $j$-th stack.

top i, Print the value of the top element of $i$-th stack. If stack is empty print “Empty!”

Input

Input starts with an integer $T$ ($1 ≤ T ≤ 5$), denoting the number of test cases.

The next line contains two integers $N$ ($1 ≤ N ≤ 10^4$), $Q$ ($1 ≤ Q ≤ 5 \times 10^4$). The next $Q$ lines will contain an operation like above mentioned.

Other constraints:

$1 ≤ i, j ≤ N$

$1 ≤ x ≤ 10^5$

Output

For each test case, print the case number in a single line. Then for each 4th type operation you should print the value or “Empty!” if the stack is empty.

Sample

Input

Output

1
3 18
push 1 1
push 2 2
push 3 3
push 3 4
top 1
top 2
top 3
put 1 3
pop 2
top 1
top 2
top 3
pop 1
top 1
pop 1
top 1
pop 1
top 1