تمامًا مثل العديد من الأشياء في هذا العالم، ليس لعنوان هذه المسألة أي معنى.

بإعطائك بيانًا غير موجه يحتوي على $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