16152번 - 트리와 가희

문제

노드의 개수가 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번째 쿼리에 대한 답을 한 줄에 하나씩 출력하라.

제한

힌트