진원이는 학생들을 한 줄로 세워 실험을 하고 있다. 처음 시각 $t = 0$에는 $0$번 학생만이 $0$번 위치에 서 있다. 여기서 위치 $k$는 해당 학생의 앞에 $k$명의 학생이 있음을 의미한다.

시각 $t = 1, 2, 3, everse extdots$마다 다음과 같은 일이 순서대로 일어난다.

1. $0$번 위치에 있던 학생이 $\lfloor t/2 \rfloor$번 위치로 이동한다.
2. 원래 $1$번 위치부터 $\lfloor t/2 \rfloor$번 위치까지 서 있던 학생들은 각각 한 칸씩 앞으로(번호가 작은 위치로) 이동한다.
3. $t$번 학생이 줄의 맨 뒤($t$번 위치)에 새로 선다.

진원이를 도와 다음 $Q$ ($1 \le Q \le 10^5$)개의 독립적인 쿼리에 답하는 프로그램을 작성하시오.

• 1 c t: 시각 $t$ 직후에 $c$번 학생은 몇 번 위치에 있는가? ($0 \le c \le t \le 10^{18}$)
• 2 x t: 시각 $t$ 직후에 $x$번 위치에 있는 학생은 몇 번 학생인가? ($0 \le x \le t \le 10^{18}$)

입력

첫째 줄에 쿼리의 개수 $Q$가 주어진다.

다음 $Q$개의 줄에는 각 쿼리를 나타내는 세 정수가 1 c t 또는 2 x t 형식으로 주어진다.

출력

각 쿼리에 대한 답을 한 줄에 하나씩 출력한다.

예제 입력 1

2
1 4 9
2 2 9

예제 출력 1

2
4

예제 입력 2

22
1 0 9
1 1 9
1 2 9
1 3 9
1 4 9
1 5 9
1 6 9
1 7 9
1 8 9
1 9 9
2 0 9
2 1 9
2 2 9
2 3 9
2 4 9
2 5 9
2 6 9
2 7 9
2 8 9
2 9 9
1 0 1000000000000000000
2 0 1000000000000000000

예제 출력 2

1
3
0
4
2
5
6
7
8
9
2
0
4
1
3
5
6
7
8
9
483992463350322770
148148148148148148

점수

• 입력 3: $Q \le 1\,000$; $t \le 100$
• 입력 4: $t \le 5\,000$
• 입력 5-8: 모든 쿼리가 1번 유형이다.
• 입력 9-12: 모든 쿼리가 2번 유형이다.