시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 1536 MB 0 0 0 0.000%

문제

높이가 N인 Perfect binary tree가 있다. 즉, 2N+1-1개의 노드로 이루어져 있다.

길이가 N인 이진수 X를 이용해서 트리에서 이동해보려고 한다. 이진수의 가장 왼쪽 비트부터 각각의 비트가 0이면 왼쪽 자식으로, 1이면 오른쪽 자식으로 방문하게 된다. 예를 들어, N = 2, X = 0 = 002 라면, 가장 왼쪽 리프 노드로 이동하게 되고, X = 3 = 112인 경우에는 가장 오른쪽 리프 노드로 이동하게 된다. X = 2 = 102인 경우에는 루트에서 오른쪽 자식으로 이동한 다음, 왼쪽 자식으로 이동하게 된다.

가장 처음에 X = 0이고, 루트만 방문한 상태이다. 이제, 다음 쿼리를 수행하는 프로그램을 작성하시오.

  • 1 C: X를 X = (X + 2C) mod 2N 으로 변경한다. 그 다음, X를 이용해 트리의 루트에서부터 방문을 시작한다.
  • 2: 지금까지 트리에서 방문한 노드의 개수를 출력한다.

입력

첫째 줄에 트리의 높이 N과 쿼리의 개수 Q가 주어진다. (1 ≤ N, Q ≤ 105)

둘재 줄부터 Q개의 줄에는 쿼리가 주어진다. (0 ≤ C < N) 2번 쿼리는 적어도 하나 주어진다.

출력

각각의 2번 쿼리마다 정답을 한 줄에 하나씩 출력한다.

예제 입력

2 9
1 0
2
1 1
2
1 0
2
1 0
1 0
2

예제 출력

3
5
6
7

힌트

출처