시간 제한메모리 제한제출정답맞힌 사람정답 비율
2.5 초 1024 MB53372967.442%

문제

출제진은 여러분들이 고통받는 모습을 즐기기에 여러분들이 그다지 보고 싶지 않은 주제들을 합쳐서 문제를 내기로 했다. NP 문제인 최장 경로 문제, XOR, 쿼리가 합쳐진 이 문제를 풀어보자!

$N$개의 정점과 $M$개의 가중치 있는 무방향 간선들로 이루어진 연결그래프 $G$가 있다. $G$에서 경로의 가중치는 일반적인 경우와 다르게 계산되는데, 지난 간선들의 가중치들을 XOR한 값이다. 한 간선을 여러 번 지나는 것이 허용되며, 이 경우 그 횟수만큼 XOR해야 함에 유의하자.

정점 $u$와 $v$에 대해 $u$에서 $v$로 가는 최대 가중치의 경로를 $u$에서 $v$로 가는 최장 경로라고 한다. 이 때, 최장 경로의 가중치를 $d(u,v)$라고 하자. $Q$번 다음과 같은 쿼리를 해결해야 한다.

  • $l$ $r$: $l \leq i < j \leq r $인 모든 $i$와 $j$에 대해, $d(i,j)$ 값들을 XOR한 값을 구한다.

입력

첫 번째 줄에 $N$, $M$, $Q$가 주어진다. $(1 \leq N,M,Q \leq 100\,000)$

이후 $M$개의 줄에 걸쳐 간선의 정보가 $u$, $v$, $w$가 주어진다. 이는 정점 $u$와 $v$를 잇는 가중치 $w$의 간선이라는 뜻이다. 양 끝점이 같은 간선이 있을 수 있으며 같은 정점 쌍을 잇는 간선이 여럿 있을 수 있음에 유의하라. $(1 \leq u,v \leq N, 0 \leq w < 2^{30})$

이후 $Q$개의 줄에 걸쳐 쿼리의 정보 $l$, $r$이 주어진다. $(1 \leq l < r \leq N)$

출력

각 쿼리의 답을 순서대로 줄바꿈으로 구분하여 출력한다.

예제 입력 1

8 10 7
1 2 662784558
3 2 195868257
3 4 294212653
4 5 299265014
6 5 72652580
6 7 29303370
7 8 183954825
2 1 752722885
5 3 197591314
8 4 877461873
4 8
5 7
6 7
2 3
7 8
3 4
2 7

예제 출력 1

0
713437792
738051848
716356296
736682272
1003204975
987493236
W3sicHJvYmxlbV9pZCI6IjIwNTU3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViY2Y1XHVjN2ExXHVkNTVjIFx1Y2ZmY1x1YjlhYyIsImRlc2NyaXB0aW9uIjoiPHA+XHVjZDljXHVjODFjXHVjOWM0XHVjNzQwIFx1YzVlY1x1YjdlY1x1YmQ4NFx1YjRlNFx1Yzc3NCBcdWFjZTBcdWQxYjVcdWJjMWJcdWIyOTQgXHViYWE4XHVjMmI1XHVjNzQ0IFx1Yzk5MFx1YWUzMFx1YWUzMFx1YzVkMCBcdWM1ZWNcdWI3ZWNcdWJkODRcdWI0ZTRcdWM3NzQgXHVhZGY4XHViMmU0XHVjOWMwIFx1YmNmNFx1YWNlMCBcdWMyZjZcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YzhmY1x1YzgxY1x1YjRlNFx1Yzc0NCBcdWQ1NjlcdWNjZDBcdWMxMWMgXHViYjM4XHVjODFjXHViOTdjIFx1YjBiNFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuIE5QIFx1YmIzOFx1YzgxY1x1Yzc3OCBcdWNkNWNcdWM3YTUgXHVhY2JkXHViODVjIFx1YmIzOFx1YzgxYywgWE9SLCBcdWNmZmNcdWI5YWNcdWFjMDAgXHVkNTY5XHVjY2QwXHVjOWM0IFx1Yzc3NCBcdWJiMzhcdWM4MWNcdWI5N2MgXHVkNDgwXHVjNWI0XHViY2Y0XHVjNzkwITxcL3A+XHJcblxyXG48cD4kTiRcdWFjMWNcdWM3NTggXHVjODE1XHVjODEwXHVhY2ZjICRNJFx1YWMxY1x1Yzc1OCBcdWFjMDBcdWM5MTFcdWNlNTggXHVjNzg4XHViMjk0IFx1YmIzNFx1YmMyOVx1ZDVhNSBcdWFjMDRcdWMxMjBcdWI0ZTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzVmMFx1YWNiMFx1YWRmOFx1Yjc5OFx1ZDUwNCAkRyRcdWFjMDAgXHVjNzg4XHViMmU0LiAkRyRcdWM1ZDBcdWMxMWMgXHVhY2JkXHViODVjXHVjNzU4IFx1YWMwMFx1YzkxMVx1Y2U1OFx1YjI5NCBcdWM3N2NcdWJjMThcdWM4MDFcdWM3NzggXHVhY2JkXHVjNmIwXHVjNjQwIFx1YjJlNFx1Yjk3NFx1YWM4YyBcdWFjYzRcdWMwYjBcdWI0MThcdWIyOTRcdWIzNzAsIFx1YzljMFx1YjA5YyBcdWFjMDRcdWMxMjBcdWI0ZTRcdWM3NTggXHVhYzAwXHVjOTExXHVjZTU4XHViNGU0XHVjNzQ0IFhPUlx1ZDU1YyBcdWFjMTJcdWM3NzRcdWIyZTQuIFx1ZDU1YyBcdWFjMDRcdWMxMjBcdWM3NDQgXHVjNWVjXHViN2VjIFx1YmM4OCBcdWM5YzBcdWIwOThcdWIyOTQgXHVhYzgzXHVjNzc0IFx1ZDVjOFx1YzZhOVx1YjQxOFx1YmE3MCwgXHVjNzc0IFx1YWNiZFx1YzZiMCBcdWFkZjggXHVkNjlmXHVjMjE4XHViOWNjXHVkMDdjIFhPUlx1ZDU3NFx1YzU3YyBcdWQ1NjhcdWM1ZDAgXHVjNzIwXHVjNzU4XHVkNTU4XHVjNzkwLjxcL3A+XHJcblxyXG48cD5cdWM4MTVcdWM4MTAgJHUkXHVjNjQwICR2JFx1YzVkMCBcdWIzMDBcdWQ1NzQgJHUkXHVjNWQwXHVjMTFjICR2JFx1Yjg1YyBcdWFjMDBcdWIyOTQgXHVjZDVjXHViMzAwIFx1YWMwMFx1YzkxMVx1Y2U1OFx1Yzc1OCBcdWFjYmRcdWI4NWNcdWI5N2MgJHUkXHVjNWQwXHVjMTFjICR2JFx1Yjg1YyBcdWFjMDBcdWIyOTQgXHVjZDVjXHVjN2E1IFx1YWNiZFx1Yjg1Y1x1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1Y2Q1Y1x1YzdhNSBcdWFjYmRcdWI4NWNcdWM3NTggXHVhYzAwXHVjOTExXHVjZTU4XHViOTdjICRkKHUsdikkXHViNzdjXHVhY2UwIFx1ZDU1OFx1Yzc5MC4gJFEkXHViYzg4IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVjZmZjXHViOWFjXHViOTdjIFx1ZDU3NFx1YWNiMFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+JGwkICRyJDogJGwgXFxsZXEgaSAmbHQ7IGogXFxsZXEgciAkXHVjNzc4IFx1YmFhOFx1YjRlMCAkaSRcdWM2NDAgJGokXHVjNWQwIFx1YjMwMFx1ZDU3NCwgJGQoaSxqKSQgXHVhYzEyXHViNGU0XHVjNzQ0IFhPUlx1ZDU1YyBcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCAkTiQsICRNJCwgJFEkXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJCgxIFxcbGVxIE4sTSxRIFxcbGVxIDEwMFxcLDAwMCkkPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1ZDZjNCAkTSRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWFjMDRcdWMxMjBcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwICR1JCwgJHYkLCAkdyRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWIyOTQgXHVjODE1XHVjODEwICR1JFx1YzY0MCAkdiRcdWI5N2MgXHVjNzg3XHViMjk0IFx1YWMwMFx1YzkxMVx1Y2U1OCAkdyRcdWM3NTggXHVhYzA0XHVjMTIwXHVjNzc0XHViNzdjXHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC4gXHVjNTkxIFx1YjA1ZFx1YzgxMFx1Yzc3NCBcdWFjMTlcdWM3NDAgXHVhYzA0XHVjMTIwXHVjNzc0IFx1Yzc4OFx1Yzc0NCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTcwIFx1YWMxOVx1Yzc0MCBcdWM4MTVcdWM4MTAgXHVjMzBkXHVjNzQ0IFx1Yzc4N1x1YjI5NCBcdWFjMDRcdWMxMjBcdWM3NzQgXHVjNWVjXHViN2ZmIFx1Yzc4OFx1Yzc0NCBcdWMyMTggXHVjNzg4XHVjNzRjXHVjNWQwIFx1YzcyMFx1Yzc1OFx1ZDU1OFx1Yjc3Yy4gJCgxIFxcbGVxIHUsdiBcXGxlcSBOLCAwIFxcbGVxIHcgJmx0OyAyXnszMH0pJDxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgJFEkXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHVjZmZjXHViOWFjXHVjNzU4IFx1YzgxNVx1YmNmNCAkbCQsICRyJFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICQoMSBcXGxlcSBsICZsdDsgciBcXGxlcSBOKSQ8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVjZmZjXHViOWFjXHVjNzU4IFx1YjJmNVx1Yzc0NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOTA0XHViYzE0XHVhZmM4XHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU1OFx1YzVlYyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjA1NTciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJGaW5kIHRoZSBYT1IiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZXJlIGlzIGEgY29ubmVjdGVkIGdyYXBoICRHJCBjb25zaXN0aW5nIG9mICROJCB2ZXJ0aWNlcyBhbmQgJE0kIHdlaWdodGVkIHVuZGlyZWN0ZWQgZWRnZXMuIEluICRHJCwgdGhlIHdlaWdodCBvZiB0aGUgcGF0aCBpcyBvYnRhaW5lZCBieSBYT1JpbmcgdGhlIHdlaWdodHMgb2YgYWxsIGVkZ2VzIGluIHRoZSBwYXRoLiBOb3RlIHRoYXQgaXQgaXMgYWxsb3dlZCB0byB3YWxrIGFsb25nIG9uZSBlZGdlIG11bHRpcGxlIHRpbWVzLCBpbiB0aGlzIGNhc2UsIHlvdSBhcmUgWE9SaW5nIHRoZSB3ZWlnaHQgdGhhdCBudW1iZXIgb2YgdGltZXMuPFwvcD5cclxuXHJcbjxwPkZvciB2ZXJ0aWNlcyAkdSQgYW5kICR2JCwgbGV0ICRkICh1LCB2KSQgYmUgdGhlIDxzdHJvbmc+bWF4aW11bSB3ZWlnaHQ8XC9zdHJvbmc+IG9mIGEgcGF0aCBmcm9tICR1JCB0byAkdiQuPFwvcD5cclxuXHJcbjxwPllvdSBuZWVkIHRvIGFuc3dlciAkUSQgcXVlcmllcyBvZiB0aGUgZm9sbG93aW5nIGZvcm06PFwvcD5cclxuXHJcbjxwPkdpdmVuICRsJCBhbmQgJHIkLCBmb3IgYWxsICRpJCBhbmQgJGokIHN1Y2ggYXMgJGwgXFxsZXEgaSAmbHQ7IGogXFxsZXEgciQsIGZpbmQgdGhlIFhPUiBvZiB0aGUgdmFsdWVzIG9mICRkIChpLCBqKSQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0aHJlZSBpbnRlZ2VycywgJE4kLCAkTSQsIGFuZCAkUSQgKCQxIFxcbGVxIE4sIE0sIFEgXFxsZXEgMTBeNSQpLjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgJE0kIGxpbmVzIGNvbnRhaW5zIHRocmVlIGludGVnZXJzLCAkdSQsICR2JCwgYW5kICR3JCwgZGVzY3JpYmluZyBhbiBlZGdlIG9mIHdlaWdodCAkdyQgY29ubmVjdGluZyB2ZXJ0aWNlcyAkdSQgYW5kICR2JCAoJDEgXFxsZSB1LCB2IFxcbGUgTiQsICQwIFxcbGUgdyAmbHQ7IDJeezMwfSQpLiBOb3RlIHRoYXQgbXVsdGlwbGUgZWRnZXMgYW5kIGxvb3BzIGFyZSA8c3Ryb25nPmFsbG93ZWQ8XC9zdHJvbmc+IGluIHRoaXMgdGFzay48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nICRRJCBsaW5lcyBkZXNjcmliZXMgb25lIHF1ZXJ5IGFuZCBjb250YWlucyB0d28gaW50ZWdlcnMgJGwkIGFuZCAkciQgKCQxIFxcbGVxIGwgJmx0OyByIFxcbGVxIE4kKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBxdWVyeSwgcHJpbnQgdGhlIGFuc3dlciBvbiBhIHNlcGFyYXRlIGxpbmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==