Әлемдегі көптеген нәрселер сияқты, бұл есептің атауының ешқандай мағынасы жоқ.

$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