트리와 쿼리

$N$개의 원소를 갖는 수열 $P=\{0, 1, 2, \cdots, N-1\}$이 있다.

수열 $P$에 대해, 트리 $T_P$는 다음과 같이 정의된다.

• 총 $N$개의 정점을 가진다.
• 1번 정점은 루트이며, $2 \le i \le N$에 대해 $i$번 정점의 부모는 $\max(P_i, 1)$번 정점이다.

아래의 쿼리를 수행하는 프로그램을 작성하라.

• $1 \ x \ a$ : $P_x, P_{x+1}, \cdots, P_N$에서 각각 $a$를 뺀다.
• $2 \ x \ y$ : 현재의 수열 $P$에 대해 정의된 트리 $T_P$에서, 두 정점 $x$와 $y$의 최소 공통 조상의 번호를 출력한다.

첫째 줄에 자연수 $N$과 $Q$가 공백으로 구분되어 주어진다.

둘째 줄부터 $Q$개의 줄에 걸쳐,$1+i$번째 줄에 i번째 쿼리를 의미하는 $3$개의 정수가 주어진다.

2번 쿼리가 주어질 때마다, 답을 줄바꿈으로 구분해 출력한다.

• $1 \le N, Q \le 10^5$
• $1 \le x, y, a \le N$