Splendid matrices are square matrices with dimensions 2ⁿ X 2ⁿ filled in a particular manner. Splendid matrices for n=1, n=2 and n=3 are shown below:

n=1
1 2
3 4

n=2 
1  2  5  6
3  4  7  8
9  10 13 14
11 12 15 16

n=3 
1  2  5  6  17 18 21 22 
3  4  7  8  19 20 23 24 
9  10 13 14 25 26 29 30 
11 12 15 16 27 28 31 32 
33 34 37 38 49 50 53 54 
35 36 39 40 51 52 55 56 
41 42 45 46 57 58 61 62 
43 44 47 48 59 60 63 64

You will be given q queries, each query being of either of the 2 types :
Type 1 : 1 n k , for the splendid matrix M with dimensions 2ⁿ X 2ⁿ, what are the values of i and j such that M(i,j)=k , i.e the value k is present in which cell of the matrix M ?
Type 2 : 2 n i j , for the splendid matrix M with dimensions 2ⁿ X 2ⁿ, what is the value of M(i,j) , i.e what value is present in the cell which lies in the i th row and j th column of the matrix M?

Input

First line consists of q denoting the number of queries. The next q lines contain either queries of type 1 (3 space separated integers 1 n k) or queries of type 2 (4 space separated integers 2 n i j ).

Output

q lines. The answer to queries of type 1 should contain 2 space separated integers i and j such that M(i,j)=k. The answer to queries of type 2 should contain a single integer denoting the value at M(i,j).

Constraints

1 < = q < = 10⁵
1 < = n < = 15
1 < = k < = 2²ⁿ
1< = i , j < = 2ⁿ