(追記) (追記ここまで)

31724번 - Hyper Tree Problem 다국어

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
4 초	1024 MB	100	64	46	67.647%

문제

$N$개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1ドル$번부터 $N$번까지 번호가 붙어 있고, 트리를 구성하는 간선 또한 주어지는 순서대로 1ドル$번부터 $N-1$번까지 번호가 붙어 있다. 각 간선에는 $W_i$의 가중치가 존재한다.

다음 두 가지 유형의 질의가 합해서 $Q$개 주어진다. 2번 쿼리가 주어질 때마다, 답을 출력하는 프로그램을 작성하라.

1 e v: $e$번 간선의 가중치 $W_e$를 $W_e\ \And \ v$로 바꾼다. $\And$는 Bitwise AND 연산을 의미한다.
2 n: $\sum_{i=1}^{N}{dist(n, i)}$를 출력한다. $dist(a, b)$는 $a$번 정점과 $b$번 정점 사이를 연결하는 유일한 경로에 포함된 간선 가중치를 모두 Bitwise OR 연산한 값이다. $a = b$인 경우에는 $dist(a, b) = 0$ 이다.

입력

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

다음 $N-1$개의 줄에는 트리의 간선 정보를 의미하는 $A_i, B_i, W_i$가 공백으로 구분되어 주어진다. 트리의 $i$번 간선이 연결하는 두 정점의 번호가 $A_i, B_i$이고, 간선의 초기 가중치는 $W_i$라는 의미이다. $(1 \le A_i < B_i \le N; 0 \le W_i < 2^{20})$

다음 $Q$개의 줄에는 아래와 같은 형식 중 하나로 쿼리에 대한 정보가 주어진다.

1 e v: $(1 \le e < N; 0 \le v < 2^{20})$
2 n: $(1 \le n \le N)$

입력에서 주어지는 수는 모두 정수이고, 2번 쿼리가 적어도 하나 이상 주어짐이 보장된다.

출력

2번 쿼리의 수행 결과를 쿼리가 주어진 순서대로 한 줄에 하나씩 출력한다.

제한

예제 입력 1

예제 출력 1

57
43
35

힌트

W3sicHJvYmxlbV9pZCI6IjMxNzI0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiSHlwZXIgVHJlZSBQcm9ibGVtIiwiZGVzY3JpcHRpb24iOiI8cD4kTiRcdWFjMWNcdWM3NTggXHVjODE1XHVjODEwXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWQyYjhcdWI5YWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWQyYjhcdWI5YWNcdWM3NTggXHVhYzAxIFx1YzgxNVx1YzgxMFx1Yzc0MCAkMSRcdWJjODhcdWJkODBcdWQxMzAgJE4kXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWJkOTlcdWM1YjQgXHVjNzg4XHVhY2UwLCBcdWQyYjhcdWI5YWNcdWI5N2MgXHVhZDZjXHVjMTMxXHVkNTU4XHViMjk0IFx1YWMwNFx1YzEyMCBcdWI2MTBcdWQ1NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyAkMSRcdWJjODhcdWJkODBcdWQxMzAgJE4tMSRcdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YmQ5OVx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWFjMDRcdWMxMjBcdWM1ZDBcdWIyOTQgJFdfaSRcdWM3NTggXHVhYzAwXHVjOTExXHVjZTU4XHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFx1YjQ1MCBcdWFjMDBcdWM5YzAgXHVjNzIwXHVkNjE1XHVjNzU4IFx1YzljOFx1Yzc1OFx1YWMwMCBcdWQ1NjlcdWQ1NzRcdWMxMWMgJFEkXHVhYzFjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gMlx1YmM4OCBcdWNmZmNcdWI5YWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0Y1x1YjljOFx1YjJlNCwgXHViMmY1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHViNzdjLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjxjb2RlPjEgZSB2PFwvY29kZT46ICRlJFx1YmM4OCBcdWFjMDRcdWMxMjBcdWM3NTggXHVhYzAwXHVjOTExXHVjZTU4ICRXX2UkXHViOTdjICRXX2VcXCBcXEFuZCBcXCB2JFx1Yjg1YyBcdWJjMTRcdWFmYmNcdWIyZTQuICRcXEFuZCRcdWIyOTQgPGEgaHJlZj1cImh0dHBzOlwvXC9rby53aWtpcGVkaWEub3JnXC93aWtpXC8lRUIlQjklODQlRUQlOEElQjhfJUVDJTk3JUIwJUVDJTgyJUIwI0FORFwiPkJpdHdpc2UgQU5EPFwvYT4gXHVjNWYwXHVjMGIwXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+PGNvZGU+MiBuPFwvY29kZT46ICRcXHN1bV97aT0xfV57Tn17ZGlzdChuLCBpKX0kXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gJGRpc3QoYSwgYikkXHViMjk0ICRhJFx1YmM4OCBcdWM4MTVcdWM4MTBcdWFjZmMgJGIkXHViYzg4IFx1YzgxNVx1YzgxMCBcdWMwYWNcdWM3NzRcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YzcyMFx1Yzc3Y1x1ZDU1YyBcdWFjYmRcdWI4NWNcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDFjIFx1YWMwNFx1YzEyMCBcdWFjMDBcdWM5MTFcdWNlNThcdWI5N2MgXHViYWE4XHViNDUwIDxhIGhyZWY9XCJodHRwczpcL1wva28ud2lraXBlZGlhLm9yZ1wvd2lraVwvJUVCJUI5JTg0JUVEJThBJUI4XyVFQyU5NyVCMCVFQyU4MiVCMCNPUlwiPkJpdHdpc2UgT1I8XC9hPiBcdWM1ZjBcdWMwYjBcdWQ1NWMgXHVhYzEyXHVjNzc0XHViMmU0LiAkYSA9IGIkXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAkZGlzdChhLCBiKSA9IDAkIFx1Yzc3NFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCAkTiRcdWFjZmMgJFEkXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkKDIgXFxsZSBOIFxcbGUgMzAwXFwgMDAwOyAxIFxcbGUgUSBcXGxlIDMwMFxcIDAwMCkkPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyAkTi0xJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMmI4XHViOWFjXHVjNzU4IFx1YWMwNFx1YzEyMCBcdWM4MTVcdWJjZjRcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTU4XHViMjk0ICRBX2ksIEJfaSwgV19pJFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkMmI4XHViOWFjXHVjNzU4ICRpJFx1YmM4OCBcdWFjMDRcdWMxMjBcdWM3NzQgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YjQ1MCBcdWM4MTVcdWM4MTBcdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwICRBX2ksIEJfaSRcdWM3NzRcdWFjZTAsIFx1YWMwNFx1YzEyMFx1Yzc1OCBcdWNkMDhcdWFlMzAgXHVhYzAwXHVjOTExXHVjZTU4XHViMjk0ICRXX2kkXHViNzdjXHViMjk0IFx1Yzc1OFx1YmJmOFx1Yzc3NFx1YjJlNC4gJCgxIFxcbGUgQV9pICZsdDsgQl9pIFxcbGUgTjsgMCBcXGxlIFdfaSAmbHQ7IDJeezIwfSkkPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyAkUSRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVkNjE1XHVjMmRkIFx1YzkxMSBcdWQ1NThcdWIwOThcdWI4NWMgXHVjZmZjXHViOWFjXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjxjb2RlPjEgZSB2PFwvY29kZT46ICQoMSBcXGxlIGUgJmx0OyBOOyAwIFxcbGUgdiAmbHQ7IDJeezIwfSkkPFwvbGk+XHJcblx0PGxpPjxjb2RlPjIgbjxcL2NvZGU+OiAkKDEgXFxsZSBuIFxcbGUgTikkPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNWQwXHVjMTFjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWMyMThcdWIyOTQgXHViYWE4XHViNDUwIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YWNlMCwgMlx1YmM4OCBcdWNmZmNcdWI5YWNcdWFjMDAgXHVjODAxXHVjNWI0XHViM2M0IFx1ZDU1OFx1YjA5OCBcdWM3NzRcdWMwYzEgXHVjOGZjXHVjNWI0XHVjOWQwXHVjNzc0IFx1YmNmNFx1YzdhNVx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD4yXHViYzg4IFx1Y2ZmY1x1YjlhY1x1Yzc1OCBcdWMyMThcdWQ1ODkgXHVhY2IwXHVhY2ZjXHViOTdjIFx1Y2ZmY1x1YjlhY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzMTcyNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ikh5cGVyIFRyZWUgUHJvYmxlbSIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFyZSBnaXZlbiBhIHRyZWUgd2l0aCAkTiQgbm9kZXMuIEVhY2ggbm9kZSZuYnNwO2Zyb20gdGhlIHRyZWUgaXMgbnVtYmVyZWQgZnJvbSAkMSQgdG8gJE4kLCBhbmQgdGhlIGVkZ2VzIGFyZSBudW1iZXJlZCBieSB0aGUgb3JkZXIgdGhleSBhcmUgZ2l2ZW4uIEVhY2ggZWRnZSBoYXMgYSB3ZWlnaHQgb2YgJFdfaSQuPFwvcD5cclxuXHJcbjxwPkEgdG90YWwgb2YgJFEkIHF1ZXJpZXMgb2YgdGhlIHR3byB0eXBlcyBhcmUgZ2l2ZW4uIFdyaXRlIGEgcHJvZ3JhbSB0byBvdXRwdXQgdGhlIGFuc3dlciB3aGVuZXZlciBhJm5ic3A7cXVlcnkgb2YgdHlwZSAyIGlzIGdpdmVuLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjxjb2RlPjEgZSB2PFwvY29kZT46IENoYW5nZSB0aGUgd2VpZ2h0ICRXX2UkIG9mIGVkZ2UgJGUkIHRvICRXX2VcXCBcXEFuZCBcXCB2JC4gJFxcQW5kJCBkZW5vdGVzIHRoZSA8YSBocmVmPVwiaHR0cHM6XC9cL2VuLndpa2lwZWRpYS5vcmdcL3dpa2lcL0JpdHdpc2Vfb3BlcmF0aW9uI0FORFwiPkJpdHdpc2UgQU5EPFwvYT4gb3BlcmF0aW9uLjxcL2xpPlxyXG5cdDxsaT48Y29kZT4yIG48XC9jb2RlPjogT3V0cHV0ICRcXHN1bV97aT0xfV57Tn17ZGlzdChuLCBpKX0kLiAkZGlzdChhLCBiKSQgaXMgdGhlIHJlc3VsdCBvZiBwZXJmb3JtaW5nIGEgPGEgaHJlZj1cImh0dHBzOlwvXC9lbi53aWtpcGVkaWEub3JnXC93aWtpXC9CaXR3aXNlX29wZXJhdGlvbiNPUlwiPkJpdHdpc2UgT1I8XC9hPiBvcGVyYXRpb24gb24gYWxsIHRoZSBlZGdlJm5ic3A7d2VpZ2h0cyBpbmNsdWRlZCBpbiB0aGUgdW5pcXVlIHBhdGggY29ubmVjdGluZyB2ZXJ0ZXggJGEkIGFuZCB2ZXJ0ZXggJGIkLiBXaGVuICRhID0gYiQsICRkaXN0KGEsIGIpID0gMCQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgJE4kIGFuZCAkUSQuICQoMiBcXGxlIE4gXFxsZSAzMDBcXCAwMDA7IDEgXFxsZSBRIFxcbGUgMzAwXFwgMDAwKSQ8XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgJE4tMSQgbGluZXMgY29udGFpbiB0aHJlZSBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgJEFfaSwgQl9pLCBXX2kkLCByZXByZXNlbnRpbmcgaW5mb3JtYXRpb24gYWJvdXQgdGhlIGVkZ2VzIG9mIHRoZSB0cmVlLiBUaGUgJGkkdGggZWRnZSBvZiB0aGUgdHJlZSBjb25uZWN0cyB2ZXJ0aWNlcyZuYnNwOyRBX2kkIGFuZCAkQl9pJCwgYW5kIHRoZSBpbml0aWFsIHdlaWdodCBvZiB0aGUgZWRnZSBpcyAkV19pJC4gJCgxIFxcbGUgQV9pICZsdDsgQl9pIFxcbGUgTjsgMCBcXGxlIFdfaSAmbHQ7IDJeezIwfSkkPFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgJFEkIGxpbmVzIGNvbnRhaW4gaW5mb3JtYXRpb24gYWJvdXQgdGhlIHF1ZXJpZXMgaW4gb25lIG9mIHRoZSBmb2xsb3dpbmcgZm9ybWF0czo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT48Y29kZT4xIGUgdjxcL2NvZGU+OiZuYnNwOyQoMSBcXGxlIGUgJmx0OyBOOyAwIFxcbGUgdiAmbHQ7IDJeezIwfSkkPFwvbGk+XHJcblx0PGxpPjxjb2RlPjIgbjxcL2NvZGU+OiAkKDEgXFxsZSBuIFxcbGUgTikkPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+QWxsIG51bWJlcnMgZ2l2ZW4gaW4gdGhlIGlucHV0IGFyZSBpbnRlZ2VycywgYW5kIGl0IGlzIGd1YXJhbnRlZWQgdGhhdCB0aGVyZSBpcyBhdCBsZWFzdCBvbmUgcXVlcnkgb2YgdHlwZSAyLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoJm5ic3A7cXVlcnkgb2YgdHlwZSAyLCBwcmludCB0aGUgcmVzdWx0Jm5ic3A7b24gYSBzZXBhcmF0ZSBsaW5lLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=