계산! 3

도현이는 인경호에서 즐겁게 헤엄치는 오리, 인덕이를 바라보다가 흥미로운 사실을 발견했다. 인경호 수면 위에서 인덕이가 멈추는 지점을 정점으로, 인덕이의 동선을 간선으로 나타내면 놀랍게도 트리가 그려진다는 사실이다!

이 사실에 매우 감명한 도현이는 인덕이가 그리는 트리를 노트에 옮겨 그린 다음, 인덕이가 트리의 각 간선을 헤엄칠 때 날개짓하는 횟수를 세어 해당 간선의 가중치로 적어 넣었다. 그리고 문득 인덕이가 이 트리로 뭔가 메시지를 보내는 것 같다고 생각한 도현이는, 이 트리에서 얻을 수 있는 모든 서로 다른 경로를 기록했다. 그리고 각 경로에 포함된 간선들의 가중치를 모두 XOR 연산하여 계산 결과가 같은 경로가 몇 개씩 있는지 세기 시작했다.

그런데 XOR 연산하기에 몰두한 도현이를 보고 동우의 장난기가 발동해버렸다. 동우는 도현이의 사각을 노려 간선의 가중치를 조금씩 바꾸기 시작했다.

• 동우: (이 간선 가중치를 바꿔볼까 ㅋㅋ)
• 도현: 어...? 계산 결과가 30인 경로는 분명 7개였는데... 계산 실수했나?

우둔한 도현이는 가중치가 바뀌었다는 사실도 모르고 XOR 연산에 몰두했다.

동우는 도현이가 XOR 연산을 잘 계산하고 있는 것인지 궁금했다. 하지만 XOR 연산을 할 줄 모르는 동우는 이 상황을 쿼리로 주면 결과를 알려주는 프로그램이 있으면 좋겠다고 생각했다.

이 프로그램을 구현해보자.

첫째 줄에 두 개의 정수 (N), (M)이 주어진다. (N)은 트리의 정점 개수, (M)은 쿼리의 개수이다.

다음 (N)-1개의 줄에는 트리에 존재하는 간선이 "(a) (b) (c)"의 형태로 주어진다. 이는 초기 트리의 (a)번 정점과 (b)번 정점 사이의 가중치가 (c)임을 나타낸다.

다음 (M)개의 줄에는 한 줄에 하나씩 쿼리가 주어진다. 쿼리의 입력은 다음 형태를 따른다.

• 1 (a) (b) (c) : 정점 (a), (b)를 연결하는 간선의 가중치를 (c)로 바꾼다. (a)와 (b)를 연결하는 간선이 존재함이 보장된다.
• 2 (c) : XOR 연산 결과가 (c)인 서로 다른 경로의 개수를 출력한다.

2번 쿼리가 주어질 때마다 경로 XOR 합이 (c)인 경로의 개수를 한 줄에 출력한다.

경로는 적어도 하나의 간선을 포함해야 하며, 역방향인 두 경로는 같은 경로로 취급한다. 즉, 정점 A에서 출발해 정점 B로 도착하는 경로와 정점 B에서 출발해 정점 A로 도착하는 두 경로는 같은 경로이므로, 1번만 센다.

• 3 ≤ (N) ≤ 100,000
• 1 ≤ (M) ≤ 200,000
• 1 ≤ (a), (b) ≤ (N), (a ≠ b)
• 1 ≤ (c) ≤ 30

XOR 연산은 배타적 논리합의 정의를 따른다.