يوجد رسم بياني متصل $G$ يتكون من $N$ رأسًا و$M$ حافة موزونة غير موجّهة. في $G$، يُحسب وزن المسار بإجراء XOR على أوزان جميع حوافه. لاحظ أنه يُسمح بالمرور عبر الحافة نفسها عدة مرات، وفي هذه الحالة يُجرى XOR على وزنها ذلك العدد من المرات.

للرأسين $u$ و$v$، لتكن $d(u,v)$ أكبر وزن لمسار من $u$ إلى $v$.

عليك الإجابة عن $Q$ استعلامًا من الشكل التالي:

مع إعطاء $l$ و$r$، أوجد XOR لجميع قيم $d(i,j)$ لكل $i$ و$j$ يحققان $l\le i<j\le r$.

الإدخال

يحتوي السطر الأول على ثلاثة أعداد صحيحة $N,M,Q$ ($1\le N,M,Q\le10^5$).

يحتوي كل سطر من الأسطر الـ $M$ التالية على ثلاثة أعداد صحيحة $u,v,w$، تصف حافة وزنها $w$ تصل بين الرأسين $u$ و$v$ ($1\le u,v\le N$، $0\le w<2^{30}$). لاحظ أن الحواف المتعددة والحلقات مسموحة في هذه المسألة.

يصف كل سطر من الأسطر الـ $Q$ التالية استعلامًا واحدًا، ويحتوي على عددين صحيحين $l$ و$r$ ($1\le l<r\le 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