#470. 1469. [balkan2007]Sheets

1469. [balkan2007]Sheets

#1469. [balkan2007]Sheets

题目描述

给你一个由N*N个小方块构成的纸片,且N是2的次幂。每个小方格从左到右,从上到下依次编号。每个小方格只放

入它自己的编号。这张纸片不断地对半折叠,先是上下折叠,还是左右折叠。直到纸片的大小变成了1*1。显然,

折叠后的纸片变成了NN的一行。我们定义S=<s1,s2,s3...,sp,...,snn>,串S由这一行的数字构成,其元素依次为

折叠后的纸片从最下方的元素到最上方的数字值。正在参加无聊会议的IT专家一时兴起开始叠纸片,然后通过上述

方法得到一串字符串。为了打发时间,专家决定找到以下两种问题的答案:

问题类型1:给出一个确定的数字x,问x和字符串S的第几个元素值相同?

问题类型2:给出一个确定的位置p,问字符串中第p个位置上的元素值为?

输入格式

第一行包括一个数字Q,问题的数量。

接下来的Q行包括3个用空格隔开的数字,T,K,V

T - 表示问题的类型( T = 1 或 2 )

K - 表示纸片的规格N是2^k

V - 如果是问题类型1,则是数字x;如果是问题类型2,则是数字p

1 <= Q <= 10^5

1 <= T <= 2

0 <= K <= 31

1 <= x , p<= N*N ,其中N=2^K

输出格式

输出应该包含Q行,每行分别为对应问题的答案

样例

样例输入

3  

1 1 4  

2 2 14  

1 2 16

样例输出

3  

15  

3  

样例解释  

K=1时纸片上的数字为  

1 2  

3 4  

则S=< 1, 3, 4, 2 >  

K=2时纸片上的数字为  

1  2  3  4  

5  6  7  8  

9  10 11 12  

13 14 15 16  

则S=< 1, 13, 16, 4, 8, 12, 9, 5, 6, 10, 11, 7, 3, 15, 14, 2 >

数据范围与提示