dasdas
Input
첫째 줄에 자연수 과 가 공백으로 구분되어 주어진다.
둘째 줄부터 개의 줄에 걸쳐,번째 줄에 i번째 쿼리를 의미하는 개의 정수가 주어진다.
Output
2번 쿼리가 주어질 때마다, 답을 줄바꿈으로 구분해 출력한다.
Constraints
Subtasks
Samples
예제 1
입력
6 9
1 6 1
1 2 1
2 6 1
1 5 1
2 1 3
2 4 6
1 5 2
2 5 5
2 6 2
출력
1
1
2
5
1
각각의 업데이트 쿼리가 주어진 후 트리의 모양은 다음과 같다.
예제 2
입력
13 5
1 12 2
2 11 12
1 2 2
2 2 9
2 2 6
출력
9
1
1