시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 512 MB 127 25 17 17.708%

문제

노드의 개수가 N개이며 루트 노드의 번호가 1인 완전 이진 트리가 있다. 루트 노드를 제외한 각 노드 i(i = 2, 3, 4, ..., N)는 ⌊i / 2⌋번 노드를 부모로 갖는다. 이때 다음 2가지 종류의 쿼리를 수행하는 프로그램을 작성하시오.

  • 1 a : a를 루트로 하는 서브트리의 노드 개수를 출력한다. 만약, 노드 a가 존재하지 않는다면 0을 출력한다.
  • 2 a : a를 루트로 하는 서브트리를 제거한다. 만약, 노드 a가 존재하지 않는다면 무시한다.

입력

첫째 줄에 완전 이진 트리의 노드 개수 N(1 ≤ N ≤ 1012111225)과 쿼리의 개수 Q(1 ≤ Q ≤ 361936)가 공백으로 구분되어 주어진다.

둘째 줄부터 Q개의 각 줄에는 문제에서 주어진 쿼리가 하나씩 주어진다. a는 1이상 N이하인 정수이며, 1번 쿼리는 최소한 하나 이상 주어지는 것이 보장된다.

출력

1번째 쿼리에 대한 답을 한 줄에 하나씩 출력하라.

예제 입력 1

12 8
1 2
1 3
2 5
2 6
1 1
1 2
2 9
1 4

예제 출력 1

7
4
7
4
2

출처

Contest > 네블컵 > 제2회 네블컵 I번