32168번 - 완전 이진 트리와 쿼리

$N$개의 정점을 가진 완전 이진 트리가 있다. 초기에는 $1$번 정점이 루트이다. $1$번 정점을 제외한 모든 정점에 대해, $x$번 정점은 $\lfloor \frac x2 \rfloor$번 정점을 부모로 가진다.

이 트리에서 다음과 같은 쿼리를 처리해 보자.

• 1 v: 트리의 루트를 $v$번 정점으로 바꾼다.
• 2 v: 현재 트리에서 $v$번 정점을 루트로 하는 서브트리에 속한 모든 정점 번호의 합을 출력한다.

첫 번째 줄에 $N$, $Q$가 공백으로 구분되어 주어진다. ($1 \le N \le 1\,000\,000\,000$; $1 \le Q \le 50\,000$)

이어서 $Q$개의 줄에 걸쳐, 각 쿼리가 주어진다. 2번 쿼리가 최소 하나 이상 주어진다. ($1 \le v \le N$)

2번 쿼리가 입력될 때마다, 쿼리의 답을 한 줄에 하나씩 출력한다.