queries-on-splendid-matrices-17

Splendid matrices are square matrices with dimensions 2^n X 2^n 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^n X 2^n, 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^n X 2^n, 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^5
1 < = n < = 15
1 < = k < = 2^2n 
1< = i , j < = 2^n

SAMPLE INPUT
6
1 1 3
2 1 1 2
1 2 14
2 2 4 3
2 3 5 3
1 3 29

SAMPLE OUTPUT
2 1
2
3 4
15
37
3 7

Source: hackerearth | Difficulty: MEDIUM


Solutions: