점핑! (Jumping!)

문제

인덱스국 문화사 : Day 1

신딩은 인덱스국에만 사는 희귀한 벌레 쿠크로치(qkroach)입니다. 인덱스국의 왕 (검열됨)은 이 벌레를 영물이라 여겨, 신딩을 위해 정 M = $2^t - 1$각형 모양의 정원을 만든 뒤 정 M각형의 꼭짓점마다 시계 방향 순서로 0, 1, ···, M − 1의 번호가 붙은 징검돌을 장식해 주었습니다. 하지만 (검열됨)의 대신들은 인덱스 트리밖에 몰랐기 때문에 신딩을 어떻게 관리해주어야 하는지 알지 못했고, 결국 이웃 나라 펜윅국의 저명한 곤충학자 뚜벤을 초빙했습니다.

뚜벤은 매우 뛰어난 학자로, 단 12일만의 연구를 통해 다음의 사실들을 알아냈습니다. 신딩은 첫째 날 0번 징검돌에 있습니다. 그리고 매일 특별한 수 k, l을 정해, 현재 있는 칸에서 시계방향 으로 $2^k$칸씩 총 l번 점프한 뒤 도착한 징검돌 위에서 잠이 듭니다.

지겨운 것을 싫어하는 신딩은 같은 징검돌을 여러 번 보게 되면 큰 스트레스를 받기 때문에, 신딩이 자주 지나간 징검돌은 새롭게 꾸며주어야 합니다. 이를 위해 뚜벤은 특정 징검돌을 지 나간 횟수를 모니터링하는 프로그램을 작성하려고 했지만, 보수 밖의 일이라 그만두었습니다.

여러분이 뚜벤을 대신하여 절망에 빠진 인덱스국 신하들을 구원하도록 합시다!

구현 세부 사항

다음 함수들을 구현하세요.

void init(int t)

• 이 함수는 처음 단 한 번 그레이더에 의해 호출됩니다.
• 정수 t는 정원의 크기를 나타냅니다. 정원의 크기 M = $2^t - 1$입니다.

void jump(int k, int l)

• 이 함수는 총 QJ 번 호출됩니다.
• 이 함수는 신딩이 $2^k$칸씩 l번 점프할 때 호출됩니다.

int64 check(int a)

• 이 함수는 총 QC 번 호출됩니다.
• 이 함수는 신딩이 a번째 징검돌을 방문한 횟수를 반환해야 합니다. 단, 신딩이 처음 밟고 있던 0번 징검돌은 방문한 것으로 세지 않습니다.

제한 조건

• 1 ≤ t ≤ 19
• 1 ≤ QJ ≤ 500,000, 1 ≤ QC ≤ 200,000
• 0 ≤ k ≤ $10^9$, 0 ≤ l ≤ $10^9$
• 0 ≤ a < M

서브태스크

서브태스크	점수	t	QJ
1	2	t ≤ 12	QJ ≤ 5,000
2	8	t ≤ 17	QJ ≤ 200,000
3	5	t ≤ 19	QJ ≤ 500,000

예제 입출력

t = 3, QJ = 1, QC = 2

그레이더는 다음 함수를 호출합니다.

init(3)

jump(1,4)

check(3) = 0

check(1) = 1

샘플 그레이더

Sample grader는 다음의 형식으로 입력을 받습니다.

• line 1 : t QJ QC
• line 2 + i (0 ≤ i ≤ QJ + QC − 1) : 1 k l (jump(k, l)) or 2 a (check(a))