JOI-kun เป็นหมูป่าที่อาศัยอยู่ในป่า IOI ซึ่งมีจุดให้อาหาร $N$ จุดและถนน $M$ สาย จุดให้อาหารมีหมายเลขตั้งแต่ $1$ ถึง $N$ ถนนสายที่ $i$ ($1\le i\le M$) เชื่อมจุดให้อาหาร $A_i$ และ $B_i$ แบบสองทิศทาง และ JOI-kun ใช้เวลา $C_i$ ชั่วโมงในการเดินทางไปตามถนนสายนี้ไม่ว่าจะไปในทิศทางใด สามารถเดินทางจากจุดให้อาหารใด ๆ ไปยังจุดอื่นได้โดยใช้ถนนอย่างน้อยหนึ่งสาย

JOI-kun ไม่ถนัดการกลับตัว เขาไม่สามารถกลับตัวกลางถนนเพื่อย้อนกลับไปยังจุดให้อาหารที่เพิ่งจากมาได้ นอกจากนี้ เมื่อเขาเดินทางตามถนนมาถึงจุดให้อาหาร เขาไม่สามารถใช้ถนนสายเดิมย้อนกลับไปยังจุดให้อาหารที่อยู่ก่อนหน้านั้นได้ทันที

ทุกวัน JOI-kun จะนำอาหารไปเติมตามจุดให้อาหารตามแผนการเติมอาหาร แผนของแต่ละวันประกอบด้วยลำดับจุดให้อาหาร $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-kun กำหนดแผนเริ่มต้นเป็น $X_1,X_2,\ldots,X_L$ ในเช้าวันที่ $k$ ($1\le k\le T$) เขาจะเปลี่ยนค่าตัวที่ $P_k$ ของแผนเป็น $Q_k$ (กล่าวคือ $X_{P_k}$ กลายเป็น $Q_k$) จากนั้นจึงเติมอาหารตามแผนใหม่ รับประกันว่าหลังการเปลี่ยนแปลงจะยังมี $X_j\ne X_{j+1}$ สำหรับทุก $j$ ($1\le j\le L-1$)

สำหรับแผนของแต่ละวันตลอด $T$ วัน JOI-kun ต้องการทราบว่าเขาสามารถทำตามแผนได้หรือไม่ และหากทำได้ ต้องการหาเวลาน้อยที่สุดที่ใช้เติมอาหารตามแผนนั้น

งาน

เมื่อกำหนดข้อมูลของป่า IOI และแผนการเติมอาหารของ JOI-kun ให้เขียนโปรแกรมที่ตรวจสอบแผนของแต่ละวันตลอด $T$ วันว่าเขาสามารถทำตามได้หรือไม่ และหากทำได้ ให้หาเวลาน้อยที่สุดที่ใช้เติมอาหารตามแผนนั้น

ข้อมูลนำเข้า

อ่านข้อมูลต่อไปนี้จากอินพุตมาตรฐาน

• บรรทัดแรกมีจำนวนเต็มสี่จำนวน $N,M,T,L$ คั่นด้วยช่องว่าง หมายความว่าป่า IOI มีจุดให้อาหาร $N$ จุดและถนน $M$ สาย JOI-kun พิจารณาแผนสำหรับ $T$ วัน และแต่ละแผนเป็นลำดับความยาว $L$
• บรรทัดที่ $i$ ($1\le i\le M$) จาก $M$ บรรทัดถัดมามีจำนวนเต็มสามจำนวน $A_i,B_i,C_i$ คั่นด้วยช่องว่าง หมายความว่าถนนสายที่ $i$ เชื่อมจุดให้อาหาร $A_i$ และ $B_i$ แบบสองทิศทาง และ JOI-kun ใช้เวลา $C_i$ ชั่วโมงเดินทางตามถนนสายนี้ไม่ว่าจะไปในทิศทางใด
• บรรทัดที่ $j$ ($1\le j\le L$) จาก $L$ บรรทัดถัดมามีจำนวนเต็ม $X_j$ หมายความว่าแผนเริ่มต้นคือ $X_1,X_2,\ldots,X_L$
• บรรทัดที่ $k$ ($1\le k\le T$) จาก $T$ บรรทัดถัดมามีจำนวนเต็มสองจำนวน $P_k,Q_k$ คั่นด้วยช่องว่าง หมายความว่า JOI-kun จะเปลี่ยนค่าตัวที่ $P_k$ ของแผนเป็น $Q_k$ ในเช้าวันที่ $k$

ข้อมูลส่งออก

เขียน $T$ บรรทัดไปยังเอาต์พุตมาตรฐาน บรรทัดที่ $k$ ($1\le k\le T$) ต้องมี $-1$ หากเขาไม่สามารถทำตามแผนของวันที่ $k$ ได้ หรือมีเวลาน้อยที่สุดเป็นชั่วโมงที่ใช้ทำตามแผนหากทำได้

ข้อจำกัด

ข้อมูลนำเข้าทั้งหมดเป็นไปตามเงื่อนไขต่อไปนี้

• $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$)
• มี $X_j\ne X_{j+1}$ สำหรับทุก $j$ ($1\le j\le L-1$) และหลังการเปลี่ยนแผนแต่ละครั้งก็ยังมี $X_j\ne X_{j+1}$ สำหรับทุก $j$ ($1\le j\le L-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-kun เปลี่ยนค่าตัวที่ 3 ของแผนเป็น $1$ ในเช้าวันแรก ดังนั้นแผนของวันแรกคือ $1,2,1$

เริ่มแรก JOI-kun เติมอาหารที่จุด $1$ จากนั้นใช้ถนนสายที่ 1 เดินทางจากจุด $1$ ไปยังจุด $2$ และเติมอาหารที่จุด $2$ ต่อมาใช้ถนนสายที่ 2 เดินทางจากจุด $2$ ไปยังจุด $3$ สุดท้ายใช้ถนนสายที่ 3 เดินทางจากจุด $3$ ไปยังจุด $1$ และเติมอาหารที่จุด $1$ วิธีนี้ใช้เวลา 3 ชั่วโมงในการทำตามแผน ซึ่งเป็นเวลาน้อยที่สุด จึงส่งออก 3

โปรดทราบว่า JOI-kun ไม่สามารถเดินทางตามจุด $1\to2\to1$ ได้ เพราะเขาไม่สามารถกลับตัวได้

ข้อมูลนำเข้า 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 แผนของวันแรกคือ $4,1,4$ เริ่มแรก JOI-kun เติมอาหารที่จุด $4$ จากนั้นใช้ถนนสายที่ 4 เดินทางจากจุด $4$ ไปยังจุด $1$ และเติมอาหารที่จุด $1$ ต่อมาใช้ถนนสายที่ 1, 2, 3 และ 4 ตามลำดับ เดินทางตามจุด $1\to2\to3\to1\to4$ แล้วเติมอาหารที่จุด $4$ วิธีนี้ใช้เวลาน้อยที่สุด

แผนของวันที่ 4 คือ $2,4,2$ เนื่องจาก JOI-kun ไม่สามารถทำตามแผนนี้ได้ จึงส่งออก -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