JOI-кун — $N$ азық бекеті мен $M$ жолы бар IOI орманында тұратын қабан. Азық бекеттері $1$-ден $N$-ге дейін нөмірленген. $i$-ші жол ($1 \le i \le M$) $A_i$ және $B_i$ азық бекеттерін екі бағытта да қосады, және JOI-кунға осы жолмен кез келген бағытта жүріп өту үшін $C_i$ сағат қажет. Бір немесе бірнеше жолды пайдаланып, кез келген азық бекетінен кез келген басқа азық бекетіне баруға болады.

JOI-кун кері бұрылуға (U-turn) шорқақ. Ол жолдың ортасында кері бұрылып, өзі шыққан азық бекетіне қайта орала алмайды. Сонымен қатар, ол бір жолды пайдаланып азық бекетіне жеткен кезде, дәл соның алдында өзі болған азық бекетіне қайта оралу үшін сол жолмен кері жүре алмайды.

Күн сайын JOI-кун азық бекеттеріне жабдықтау жоспарына сәйкес азық жеткізеді. Бір күнге арналған жабдықтау жоспары $L$ азық бекетінің $X_1,X_2,\ldots,X_L$ тізбегінен тұрады. Ол жабдықтауды $X_1$ азық бекетінен бастайды, азық бекеттеріне осы ретпен барады және жабдықтауды $X_L$ азық бекетінде аяқтайды. Оған ортасында басқа азық бекеттері арқылы өтуге рұқсат етіледі. Ол бір азық бекетін бірнеше рет жабдықтауы мүмкін, бірақ әрбір $j$ ($1 \le j \le L-1$) үшін $X_j \ne X_{j+1}$ шарты орындалады. Айта кетейік, ол орындай алмайтын жабдықтау жоспары да болуы мүмкін.

Басында JOI-кун бастапқы $X_1,X_2,\ldots,X_L$ жабдықтау жоспарын анықтайды. Ол $k$-ші күннің ($1 \le k \le T$) таңында жабдықтау жоспарының $P_k$-ші мәнін $Q_k$ мәніне өзгертеді (яғни $X_{P_k}$ мәні $Q_k$ болады), содан кейін жаңа жабдықтау жоспарына сәйкес азық жеткізеді. Өзгерістен кейін де әрбір $j$ ($1 \le j \le L-1$) үшін $X_j \ne X_{j+1}$ шарты орындалатынына кепілдік беріледі.

$T$ күннің әрбір жабдықтау жоспары үшін JOI-кун сол жабдықтау жоспарын орындай алатынын немесе орындай алмайтынын анықтағысы келеді, ал егер орындай алса, жабдықтау жоспарына сәйкес азық жеткізуге кететін ең аз мүмкін уақытты тапқысы келеді.

Тапсырма

IOI орманының деректері және JOI-кунның жабдықтау жоспарлары берілген, $T$ күннің әрбір жабдықтау жоспары үшін оның жабдықтау жоспарын орындай алатынын немесе орындай алмайтынын анықтайтын, ал егер орындай алса, жабдықтау жоспарына сәйкес азық жеткізуге кететін ең аз мүмкін уақытты табатын программа жазыңыз.

Кіріс деректер

Стандартты енгізуден келесі деректерді оқыңыз.

• Кіріс деректердің бірінші қатарында бос орын арқылы бөлінген төрт бүтін сан $N$, $M$, $T$ және $L$ берілген. Бұл IOI орманында $N$ азық бекеті мен $M$ жол бар екенін, JOI-кун $T$ күнге арналған жабдықтау жоспарларын қарастыратынын және жабдықтау жоспары ұзындығы $L$ тізбектен тұратынын білдіреді.
• Келесі $M$ қатардың $i$-ші қатарында ($1 \le i \le M$) бос орын арқылы бөлінген үш бүтін сан $A_i$, $B_i$ және $C_i$ берілген. Бұл $i$-ші жол $A_i$ және $B_i$ азық бекеттерін екі бағытта да қосатынын және JOI-кунға осы жолмен кез келген бағытта жүріп өту үшін $C_i$ сағат қажет екенін білдіреді.
• Келесі $L$ қатардың $j$-ші қатарында ($1 \le j \le L$) $X_j$ бүтін саны берілген. Бұл бастапқы жабдықтау жоспары $X_1,X_2,\ldots,X_L$ екенін білдіреді.
• Келесі $T$ қатардың $k$-ші қатарында ($1 \le k \le T$) бос орын арқылы бөлінген екі бүтін сан $P_k$ және $Q_k$ берілген. Бұл JOI-кун $k$-ші күннің таңында жабдықтау жоспарының $P_k$-ші мәнін $Q_k$ мәніне өзгертетінін білдіреді.

Шығыс деректер

Стандартты шығаруға $T$ қатар жазыңыз. $k$-ші қатарда ($1 \le k \le T$), егер ол $k$-ші күні жабдықтау жоспарын орындай алмаса $-1$, ал егер орындай алса, оны орындауға кететін сағатпен есептелген ең аз мүмкін уақыт болуы керек.

Шектеулер

Барлық кіріс деректер келесі шарттарды қанағаттандырады.

• $2 \le N \le 2\,000$.
• $N-1 \le M \le 2\,000$.
• $1 \le T \le 100\,000$.
• $2 \le L \le 100\,000$.
• $1 \le A_i < B_i \le N$ ($1 \le i \le M$).
• $(A_i,B_i) \ne (A_j,B_j)$ ($1 \le i < j \le M$).
• Бір немесе бірнеше жолды пайдаланып, кез келген азық бекетінен кез келген басқа азық бекетіне баруға болады.
• $1 \le C_i \le 1\,000\,000\,000$ ($1 \le i \le M$).
• $1 \le X_j \le N$ ($1 \le j \le L$).
• $1 \le P_k \le L$ ($1 \le k \le T$).
• $1 \le Q_k \le N$ ($1 \le k \le T$).
• Әрбір $j$ ($1 \le j \le L-1$) үшін $X_j \ne X_{j+1}$ шарты орындалады. Сондай-ақ жабдықтау жоспарының әрбір өзгерісінен кейін де әрбір $j$ ($1 \le j \le L-1$) үшін $X_j \ne X_{j+1}$ шарты орындалады.

Ішкі есептер

Барлығы 4 ішкі есеп бар. Әрбір ішкі есептің ұпайы мен қосымша шектеулері келесідей:

Ішкі есеп 1 [12 ұпай]

• $N \le 10$.
• $M \le 10$.
• $T=1$.
• $L \le 10$.
• $C_i \le 10$ ($1 \le i \le M$).

Ішкі есеп 2 [35 ұпай]

• $N \le 500$.
• $M \le 500$.
• $T=1$.

Ішкі есеп 3 [15 ұпай]

• $T=1$.

Ішкі есеп 4 [38 ұпай]

Қосымша шектеулер жоқ.

Мысалдар

Кіріс деректер 1

3 3 1 3
1 2 1
2 3 1
1 3 1
1
2
3
3 1

Шығыс деректер 1

3

Ескертпе

1-мысалда бастапқы жабдықтау жоспары — $1,2,3$. JOI-кун 1-ші күннің таңында осы жабдықтау жоспарының 3-ші мәнін $1$-ге өзгертеді. Сондықтан 1-ші күнгі жабдықтау жоспары — $1,2,1$.

Алдымен JOI-кун $1$ азық бекетіне азық жеткізеді. Келесіде ол $1$ азық бекетінен $2$ азық бекетіне бару үшін 1-ші жолды пайдаланады және $2$ азық бекетіне азық жеткізеді. Содан кейін ол $2$ азық бекетінен $3$ азық бекетіне бару үшін 2-ші жолды пайдаланады. Соңында ол $3$ азық бекетінен $1$ азық бекетіне бару үшін 3-ші жолды пайдаланады және $1$ азық бекетіне азық жеткізеді. Осылайша, жабдықтау жоспарын орындауға 3 сағат кетеді. Бұл ең аз мүмкін уақыт болғандықтан, 3 шығарыңыз.

Ескерту: JOI-кун азық бекеттері арасында $1 \to 2 \to 1$ болып қозғала алмайды, себебі ол кері бұрыла алмайды.

Кіріс деректер 2

4 4 4 3
1 2 1
2 3 1
1 3 1
1 4 1
4
1
3
3 4
1 2
3 2
2 4

Шығыс деректер 2

5
2
3
-1

Ескертпе

2-мысалда 1-ші күнгі жабдықтау жоспары — $4,1,4$. Алдымен JOI-кун $4$ азық бекетін жабдықтайды. Келесіде ол $4$ азық бекетінен $1$ азық бекетіне бару үшін 4-ші жолды пайдаланады және $1$ азық бекетіне азық жеткізеді. Содан кейін ол азық бекеттері арасында $1 \to 2 \to 3 \to 1 \to 4$ болып қозғалу үшін 1-ші, 2-ші, 3-ші және 4-ші жолдарды осы ретпен пайдаланады және $4$ азық бекетіне азық жеткізеді. Бұл ең аз мүмкін уақытты алады.

4-ші күнгі жабдықтау жоспары — $2,4,2$. JOI-кун бұл жабдықтау жоспарын орындай алмайтындықтан, -1 шығарыңыз.

Кіріс деректер 3

5 6 1 5
1 2 8
1 3 8
1 4 8
2 5 2
3 4 6
4 5 6
2
5
1
5
3
5 2

Шығыс деректер 3

38