Time Limit: 1000 MS    Memory Limit: 65536 K 


Description

baihacker is soooooo angry about that somebody is jumping the queue. While somebody is queueing, the ones who come late make another queue, so it take him more time to queue. Then the worker comes up to merge the queues into one, but he does not know which queue comes first, so he develop a special gate to merge two queues into one. There are 2^n queues numberd from 0 to 2^n-1 from left to right. He merge the first two queues into one, the the seond two, and so on. Then remain 2^(n-1) queues, so he repeating doing this until there is only one queue. The sepcial gate allow the first k person of his left queue pass the gate, then the right queue, and so on. When a person in the ith queue and he is the jth person of the queue, we call i is his queue-id, and j is his queue-position. After merging the queues, he is the ith person and we call i is his global-id. We assume there are infinite people in each queue, so given n, k and the global-position of a person, what's the queue-id and queue-position of him, and given the queue-id and queue-position of him, what's the global-position.

Input

For each inputfile, the first is a number X stands for the query type. Then a number T in the follow stands for the number of test cases. And then T lines follow. When X is equal to zero, each lines contains 3 integers seperated by a space: n, k, global-position. When X is equal to one, each lines contains 4 integers seperated by a space: n, k, queue-id, queue-position. constraints: X is always equal to 0 or 1. n is in the range of [0, 32]. k is in the range of [1, 32]. global-position is in the range of [0, 10^15). The associated queue-id, queue-position is always valid.

Output

When X is equal to 0, output n k queue-id queue-position in a single line and seperated by a space. When X is equal to 1, output n k global-position in a single line and seperated by a space.

Sample Input

0 11 7 2 0 7 2 1 7 2 2 7 2 3 7 2 4 7 2 5 7 2 6 7 2 7 7 2 8 7 2 9 7 32 123456789123456

Sample Output

7 2 0 0 7 2 0 1 7 2 64 0 7 2 64 1 7 2 32 0 7 2 32 1 7 2 96 0 7 2 96 1 7 2 16 0 7 2 16 1 7 32 24 964506165024

Author

baihacker