בדיוק כמו דברים רבים בעולם, לכותרת של בעיה זו אין שום משמעות.

נתון גרף לא מכוון עם $n$ קודקודים ו-$m$ קשתות; הקשתות ממוספרות מ-$1$ עד $m$ לפי הסדר, ולכל קשת יש משקל $c_i$. כעת עליכם לענות על $q$ שאילתות, כל אחת מהצורה הבאה:

• אם משאירים רק את הקשתות שהאינדקסים שלהן נמצאים ב-$[l, r]$, מהו סכום המשקלים של כל קשתות הגשר בגרף מודולו $2^{64}$?

עליכם לענות על כל שאילתה.

אולי תרצו לדעת את ההגדרה של גשר: קשת נקראת גשר אם ורק אם הסרתה מגדילה את מספר הרכיבים הקשירים בגרף.

קלט

השורה הראשונה מכילה את $n, m, q$ ($1 \le n \le 500$, $1 \le m, q \le 10^5$), המייצגים את מספר הקודקודים, הקשתות והשאילתות בגרף.

$m$ השורות הבאות מכילות כל אחת שלושה מספרים שלמים $u, v, c$ ($1 \le u, v \le n$, $0 \le c < 2^{64}$), המייצגים קשת בגרף.

$q$ השורות הבאות מכילות כל אחת שני מספרים שלמים חיוביים $l, r$ ($1 \le l \le r \le m$), המייצגים שאילתה.

מובטח כי הגרף אינו מכיל לולאות עצמיות, אך הוא עשוי להכיל קשתות כפולות.

פלט

עבור כל שאילתה, הדפיסו שורה אחת המכילה מספר שלם המייצג את התשובה.

דוגמה

קלט 1

5 6 6
1 2 1
2 3 2
2 4 4
2 5 8
1 3 16
4 5 32
1 3
2 4
3 5
4 6
2 6
1 6

פלט 1

7
14
28
56
18
0