Quốc gia Alpha có một trang trại điện gió được quy hoạch bởi một bảng vuông ~N~ hàng và ~N~ cột. Các hàng được đánh số từ 1 tới ~N~ từ trên xuống dưới, các cột được đánh số từ ~1~ tới ~N~ từ trái sang phải. Trang trại có ~M~ trạm sản xuất điện gió được đánh số từ ~1~ tới ~M~. Trạm thứ ~i~ (~1 \le i \le M~) được đặt tại ô thuộc hàng ~R_i~, cột ~C_i~ và có công suất sản xuất là ~W_i~ oát. Chủ trang trại mới ký hợp đồng cung cấp điện cho đối tác. Trang trại sẽ phải lắp ba đường truyền điện, mỗi đường truyền đi qua một hàng hoặc một cột trong bảng. Các đường truyền có thể cắt nhau nhưng không được trùng nhau. Tổng công suất cung cấp cho đối tác là tổng công suất của các trạm điện nằm trên ít nhất một trong ba đường truyền. Trang trại cần tìm ra cách lắp đặt ba đường truyền để tổng công suất cung cấp là lớn nhất có thể.

Ngoài ra, công ty có ~Q~ phương án điều chỉnh. Phương án điều chỉnh thứ ~j~ (~1 \le j \le Q~) là tăng công suất của trạm ~T_j~ thêm một lượng ~D_j~ oát và giữ nguyên công suất ~W_i~ oát như hiện trạng ban đầu của mọi trạm ~i~ khác ~T_j~. Lưu ý, các phương án là độc lập, nghĩa là các phương án đều chỉ áp dụng lên hiện trạng ban đầu của trang trại.

Yêu cầu: Hãy đưa ra tổng công suất lớn nhất có thể khi lắp ba đường truyền với hiện trạng ban đầu của trang trại và trong ~Q~ phương án điều chỉnh.

Input

Vào từ file văn bản THREE.INP:

• Dòng đầu ghi một số nguyên dương ~\mathcal{T}~ là số lượng trường hợp test.

• Mỗi nhóm dòng trong số ~\mathcal{T}~ nhóm dòng tiếp theo mô tả một trường hợp test có cấu trúc như sau:

  — Dòng thứ nhất chứa ba số nguyên ~N~, ~M~ và ~Q~ lần lượt là kích thước bảng, số lượng trạm điện và số lượng phương án điều chỉnh (~3 \le N \le 10^9~; ~3 \le M \le 10^5~; ~1 \le Q \le 10^5~).

  — Dòng thứ ~i~ trong số ~M~ dòng tiếp theo chứa ba số nguyên ~R_i~, ~C_i~, và ~W_i~ lần lượt là vị trí hàng, vị trí cột và công suất của trạm điện thứ ~i~. Dữ liệu bảo đảm không có hai trạm nào đặt tại cùng một ô (~1 \le R_i, C_i \le N~; ~1 \le W_i \le 10^9~).

  — Dòng thứ ~j~ trong số ~Q~ dòng tiếp theo chứa hai số nguyên ~T_j~ và ~D_j~ thể hiện phương án điều chỉnh tăng công suất thêm ~D_j~ oát cho trạm điện thứ ~T_j~ (~1 \le T_j \le M~; ~1 \le D_j \le 10^{18}~).

Gọi ~\sum_M~ và ~\sum_Q~ tương ứng là tổng của tất cả các giá trị ~M~ và ~Q~ trong tất cả ~\mathcal{T}~ trường hợp test. Dữ liệu đảm bảo ~1 \le \sum_M~, ~\sum_Q \le 2 \times 10^5~.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

Ghi ra file văn bản THREE.OUT:

• Gồm ~\mathcal{T}~ nhóm dòng, mỗi dòng là kết quả của trường hợp test tương ứng có cấu trúc sau:

  — Dòng thứ nhất ghi ra một số nguyên dương là tổng công suất lớn nhất tìm được với hiện trạng trang trại ban đầu.

  — Dòng thứ ~j~ trong số ~Q~ dòng tiếp theo ghi ra tổng công suất lớn nhất tìm được với phương án điều chỉnh thứ ~j~.

Scoring

Subtask	Điểm	Giới hạn
1	~20\%~	~N, M, Q \le 40~ và ~\mathcal{T} = 1~.
2	~20\%~	~N, M, Q \le 100~ và ~\mathcal{T} = 1~.
3	~20\%~	~N, M, Q \le 500~ và ~\mathcal{T} = 1~.
4	~20\%~	~M, Q \le 1000~ và ~\sum_M, \sum_Q \le 2000~.
5	~10\%~	~M \le 1000~ và ~\sum_M \le 2000~.
6	~10\%~	Không có ràng buộc gì thêm.

Sample Input 1

2
5 7 2
1 1 1
3 1 2
2 2 3
4 2 4
2 4 2
1 5 5
3 5 2
5 3
2 7
3 3 1
1 1 1
1 2 2
1 3 3
3 1

Sample Output 1

17
19
24
6
7

Notes

Xét trường hợp test thứ nhất:

— Với hiện trạng ban đầu, một cách tối ưu là lắp ba đường truyền ở cột ~1~, cột ~2~ và cột ~5~. Tổng công suất cung cấp là ~17~.

— Với phương án điều chỉnh thứ nhất, một cách tối ưu là lắp ba đường truyền ở hàng ~2~, cột ~2~ và cột ~5~. Tổng công suất cung cấp là ~19~.

— Với phương án điều chỉnh thứ hai, một cách tối ưu là lắp ba đường truyền ở hàng ~1~, hàng ~3~ và cột ~2~. Tổng công suất cung cấp là ~24~.

Quốc gia ~Beta~ có ~N~ thành phố được đánh số từ ~1~ đến ~N~. Các thành phố được nối với nhau bởi ~M~ con đường hai chiều, được đánh số từ ~1~ đến ~M~, giữa hai thành phố bất kỳ có tối đa một con đường nối trực tiếp chúng. Con đường hai chiều số ~i~ ~(1 \le i \le M)~ nối trực tiếp giữa hai thành phố phân biệt ~U_i~ và ~V_i~ có độ dài ~W_i~. Một đường đi gồm ~K~ thành phố từ thành phố ~X~ tới thành phố ~Y~ là một chuỗi các thành phố ~P_1, P_2, \dots, P_k,~ sao cho ~P_1 = X~, ~P_k = Y~ và có con đường trực tiếp giữa hai thành phố ~P_i~ và ~P_{i + 1}~ ~(\forall i = 1, 2, \dots, K - 1)~. Ở quốc gia ~Beta~, mọi thành phố đều có đường đi tới thành phố khác. Chi phí di chuyển của một đường đi từ ~X~ tới thành phố ~Y~ là tổng độ dài của các con đường trên đường đi đó. Gọi ~D(X, Y)~ là chi phí di chuyển nhỏ nhất trong số các chi phí di chuyển của các đường đi từ thành phố ~X~ tới thành phố ~Y~. Quy ước ~D(X, X) = 0~ với mọi thành phố ~X~.

Thành phố số ~1~ có một nhà máy đúc khuôn và thành phố số ~2~ có một nhà máy sản xuất mạ tĩnh điện. Một doanh nghiệp muốn chọn một thành phố nào đó để mở một trung tâm chế tạo thép trang trí sử dụng nguyên liệu từ nhà máy đúc khuôn và nhà máy sản xuất mạ tĩnh điện. Thành phố ~Y~ được gọi là tốt hơn hoặc tương đương với thành phố ~X~ khi và chỉ khi ~D(Y, 1) \le D(X, 1)~ và ~D(Y, 2) \le D(X, 2)~. Lưu ý, thành phố ~X~ được xem là tố hơn hoặc tương đương so với chính nó. Doanh nghiệp tính hạng của thành phố ~X~ là số lượng thành phố ~Y~ tốt hơn hoặc tương đương so với thành phố ~X~. Cụ thể, công thức tính hạng là:

$$R(X) = |\{Y \in \{1, 2, \dots, N\} : D(Y, 1) \le D(X, 1) \text{ và } D(Y, 2) \le D(X, 2) \}|$$

Ngoài ra, doanh nghiệp cũng cam kết với chính quyền địa phương rằng trước khi đặt trung tâm chế tạo thép ở thành phố ~X~ nào đó, họ sẽ cải tạo một con đường nối với thành phố ~X~. Doanh nghiệp đã khảo sát và đứa ra ~P~ phương án. Với Phương án thứ ~j~ ~(1 \le j \le P)~. Với phương án thứ ~j~ ~(1 \le j \le P)~, con đường ~T_j~ nối giữa thành phố ~U_{T_j}~ và ~V_{T_j}~ sẽ được chọn để cải tạo giúp cho độ dài mới ~W_{T_j}'~ bé hơn độ dài ban đầu ~W_{T_j}~. Với mỗi phương án, sau khi cải tạo đường, doanh nghiệp cần tính hạng của thành phố ~U_{T_j}~ và thành phố ~V_{T_j}~. Các phương án là độc lập, nghĩa là các phương án đều chỉ áp dụng lên hiện trạng ban đầu của ~M~ con đường.

~\textbf{Yêu cầu:}~ Với phương án thứ ~j~ ~(1 \le j \le P)~, hãy giúp doanh nghiệp tìm ra hạng của thành phố ~U_{T_j}~ và thành phố ~V_{T_j}~ sau khi cải tạo con đường ~T_j~.

Input

Vào từ file văn bản ~\texttt{IMPEVAL.INP}~:

– Dòng đầu chứa ba số nguyên ~N, M~ và ~P~ lần lượt là số lượng thành phố, số lượng con đường và số lượng phương án ~(2 \le N \le 10^5; 1 \le M, P \le 10^5).~

– Dòng thứ ~i~ trong số ~M~ dòng tiếp theo chứa ba số nguyên ~U_i~, ~V_i~ và ~W_i~ lần lượt là hai thành phố được nối bởi con đường số ~i~ và độ dài của con đường này ~(1 \le U_i, V_i \le N; 1 \le W_i \le 10^9).~

– Dòng thứ ~j~ trong số ~P~ dòng tiếp theo chứa hai số nguyên ~T_j~ và ~W_{T_j}'~ lần lượt là chỉ số con đường được lên phương án cải tạo và độ dài sau khi cải tạo ~(1 \le T_j \le M; 1 \le W_{T_j}' < W_{T_j}).~

Output

Ghi ra file văn bản ~\texttt{IMPEVAL.OUT}~:

– Gồm ~P~ dòng, trong đó dòng thứ ~j~ ghi ra hai số nguyên ~R(U_{T_j})~ và ~R(V_{T_j})~ tương ứng là hạng của thành phố ~U_{T_j}~ và thành phố ~V_{T_j}~ nếu phương án thứ ~j~ được triển khai.

Scoring

Subtask	Điểm	Giới hạn
1	~20\%~	~M, P \le 1000~
2	~20\%~	Mỗi thành phố có nhiều nhất 2 con đường nối với thành phố khác
3	~20\%~	Mọi con đường đều nối với thành phố số 1 hoặc thành phố số 2
4	~20\%~	~M = N - 1~
5	~20\%~	Không có ràng buộc gì thêm

Sample Input 1

5 6 2
1 5 8
5 2 10
1 3 6
3 2 12
3 4 3
4 2 11
5 2
6 9

Sample Output 1

1 2
1 1

Notes

– Với con đường số ~5~ có độ dài mới bằng ~2~, thành phố số ~3~ có hạng ~1~ do chỉ có duy nhất thành phố số ~3~ tốt hơn hoặc tương đương với thành phố số ~3~, thành phố số ~4~ có hạng ~2~ do có hai thành phố tốt hơn hoặc tương đương với nó là thành phố số ~4~ và thành phố số ~5~.

X	1	2	3	4	5
D(X, 1)	0	18	6	8	8
D(X, 2)	18	0	12	11	10

– Với con đường số ~6~ có độ dài mới bằng ~9~, thành phố số ~4~ và thành phố ~2~ đều có hạng ~1~.

| |

Lần lượt minh họa cho truy vấn 1 và 2.

Quốc gia Delta có nền nông nghiệp hàng đầu thế giới. Năm nay, nhờ ứng dụng công nghệ thông tin sâu rộng trong sản xuất nông nghiệp, nông dân quốc gia Delta đã được mùa lớn. Để chúc mừng thành công lớn của bà con cũng như đẩy mạnh việc xuất khẩu, chính phủ quyết định bố trí các xe thu mua nông sản từ khắp mọi nơi trên cả nước.

Trong quốc gia có ~N~ ngôi làng được đánh số từ ~1~ đến ~N~. Mạng lưới giao thông tại đây gồm ~N - 1~ con đường hai chiều, mỗi con đường nối trực tiếp hai ngôi làng nào đó. Các con đường này bảo đảm sự liên thông toàn quốc. Nói cách khác, từ một ngôi làng bất kỳ có thể đi tới tất cả các ngôi làng còn lại thông qua một hoặc nhiều con đường. Người dân tại quốc gia Delta có khả năng sản xuất được ~K~ loại nông sản khác nhau, được đánh số từ ~1~ đến ~K~. Năm nay, người dân tại ngôi làng thứ ~i~ (~1\leq i \leq N~) sản xuất loại nông sản thứ ~A_i~.

Chính phủ quốc gia Delta sẽ bố trí ~\frac{N \cdot (N - 1)}{2}~ xe tải đi thu mua nông sản. Cụ thể, với mỗi cặp số nguyên (~u, v~) sao cho ~1 \leq u < v \leq N~, có một xe tải xuất phát từ ngôi làng thứ ~u~, đi qua một hoặc nhiều con đường rồi dừng lại ở ngôi làng thứ ~v~. Biết rằng, xe tải luôn chọn đi theo tuyến đường qua ít con đường nhất có thể, và khi tới bất kỳ một ngôi làng nào (bao gồm cả hai ngôi làng thứu ~u~ và thứ ~v~), xe tải sẽ thu mua ~1~ tấn nông sản được sản xuất tại ngôi làng đó. Nhờ mùa màng bội thu, tất cả các ngôi làng đều có đủ nông sản cho mọi xe đi qua thu mua.

Việc vận chuyển nông sản luôn phát sinh chi phí. Tùy theo đặc tính, chi phí vận chuyển từng loại nông sản có thể khác nhau. Theo tính toán của chính phủ, nếu trong toàn bộ hành trình, một xe tải thu mua được khối lượng nông sản các loại thứ ~1, 2, \ldots, K~ tương ứng là ~W_1, W_2, \ldots, W_K~ tấn, chi phí vận chuyển của xe này là ~C_1 \cdot W_1^2 + C_2 \cdot W_2^2 + \ldots + C_K \cdot W_K^2~, trong đó ~C_1, C_2, \ldots, C_K~ tương ứng là hệ số chi phí vận chuyển của ~K~ loại nông sản thứ ~1, 2, \ldots, K~. Chính phủ sẽ tài trợ toàn bộ chi phí vận chuyển, nên cần biết tổng chi phí của tất cả ~\frac{N \cdot (N - 1)}{2}~ xe tải này.

Ngoài ra, với niềm tin rằng nền nông nghiệp còn phát triển mạnh trong nhiều năm về sau, chính phủ muốn dự trù chi phí vận chuyển nông sản cho nhứng năm tiếp theo. Theo kế hoạch canh tác trong ~Q~ năm tiếp theo, vào năm thứ ~j~, (~1 \leq j \leq Q~), ngôi làng thứ ~T_j~ sẽ chuyển qua sản xuất loại nông sản thứ ~B_j~, trong khi ~N - 1~ ngôi làng còn lại sẽ tiếp tục canh tác loại nông sản như năm thứ ~j - 1~ (năm nay được coi là năm thứ ~0~). Với mỗi năm, chính phủ muốn biết tổng chi phí vận chuyển nông sản nếu tiếp tục bố trí các xe tải thu mua như phương án ở trên.

Yêu cầu: Hãy viết chương trình tính tổng chi phí vận chuyển nông sản của chính phủ trong năm nay và trong ~Q~ năm tiếp theo, dựa trên kế hoạch thay đổi canh tác.

Input

Vào từ file văn bản FBUY.INP:

• Dòng đầu chứa ba số nguyên ~N, K~ và ~Q~ lần lượt là số ngôi làng của quốc gia Delta, số loại nông sản được sản xuất tại đây và số năm trong kế hoạch canh tác (~1 \leq K \le 20~, ~1 \leq N, Q, \leq 2 \cdot 10^5~).

• Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, \ldots, A_N~ thể hiện loại nông sản chuyên được sản xuất tại các ngôi làng trong năm nay (~1 \leq A_i \leq K~, ~\forall i = 1, 2, \ldots, N~).

• Dòng thứ ba chứa ~K~ số nguyên ~C_1, C_2, \ldots,C_k~ là hệ số chi phí vận chuyển của các loại nông sản (~1 \leq C_i \leq 10^9~, ~\forall i = 1, 2, \ldots K~)

• Mỗi dòng trong số ~N - 1~ dòng tiếp theo chứa hai số nguyên ~x~ và ~y~ cho biết có một con đường hai chiều nối ngôi làng thứ ~x~ và ngôi làng thứ ~y~.

• Dòng thứ ~j~ trong số ~Q~ dòng cuối cùng chứa hai số nguyên ~T_j~ và ~B_j~ với ý nghĩa: Vào năm thứ ~j~ trong ~Q~ năm tiếp theo, ngôi làng thứ ~T_j~ sẽ chuyển sang sản xuất loại nông sản thứ ~B_j~ (~1 \leq T_j \leq N~; ~1 \leq B_j \leq K~).

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

Ghi ra file văn bản FBUY.OUT:

• Dòng đầu chứa một số nguyên là phần dư của tổng chi phí vận chuyển nông sản trong năm nay trong phép chia cho ~998244353~.

• Dòng thứ ~j~ trong số ~Q~ dòng còn lại chứa một số nguyên là phần dư của tổng chi phí vận chuyển nông sản trong năm thứ ~j~ trong phép chia cho ~998244353~.

Scoring

Subtask	Điểm	Giới hạn
1	~7,5~	~N \leq 30~ và ~Q \leq 800~
2	~12,5~	~N \leq 100~ và ~Q \leq 800~
3	~10~	~N \leq 2000~ và ~Q \leq 800~
4	~15~	~N \leq 5000~ và ~Q \leq 8000~
5	~17,5~	Luôn tồn tại một con đường nối ngôi làng thứ ~i~ và ngôi làng thứ ~\lfloor \frac{i}{2} \rfloor, \forall i = 2, 3, \ldots, N~ (~\lfloor \frac{i}{2} \rfloor~ là số nguyên lớn nhất không vượt quá ~i / 2~)
6	~22,5~	Luôn tồn tại một con đường nối ngôi làng thứ ~i~ và ngôi làng thứ ~i - 1~, ~\forall i = 2, 3, \ldots, N~
7	~15~	Không có ràng buộc gì thêm

Sample Input 1

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

Sample Output 1

120
137
139

Notes

Trong năm nay, các ngôi làng thứ ~1, 2, 3, 4, 5~ lần lượt sản xuất các loại nông sản thứu ~1, 1, 1, 2, 3~. Có tất cả ~\frac{5 \cdot (5 - 1)}{2} = 10~ xe tải với các lộ trình vận chuyển và chi phí như sau:

Các ngôi làng đi qua	Lượng nông sản thu mua theo tấn (loại ~1~, loại ~2~, loại ~3~)	Chi phí vận chuyển
~1 \rightarrow 2~	(~2, 0, 0~)	~2 \cdot 2 ^ 2 + 3 \cdot 0 ^ 2 + 5 \cdot 0 ^ 2 = 8~
~1 \rightarrow 2 \rightarrow 3~	(~3, 0, 0~)	~2 \cdot 3 ^ 2 + 3 \cdot 0 ^ 2 + 5 \cdot 0 ^ 2 = 18~
~1 \rightarrow 2 \rightarrow 4~	(~2, 1, 0~)	~2 \cdot 2 ^ 2 + 3 \cdot 1 ^ 2 + 5 \cdot 0 ^ 2 = 11~
~1 \rightarrow 5~	(~1, 0, 1~)	~2 \cdot 1 ^ 2 + 3 \cdot 0 ^ 2 + 5 \cdot 1 ^ 2 = 7~
~2 \rightarrow 3~	(~2, 0, 0~)	~2 \cdot 2 ^ 2 + 3 \cdot 0 ^ 2 + 5 \cdot 0 ^ 2 = 8~
~2 \rightarrow 4~	(~1, 1, 0~)	~2 \cdot 1 ^ 2 + 3 \cdot 1 ^ 2 + 5 \cdot 0 ^ 2 = 5~
~2 \rightarrow 1 \rightarrow 5~	(~2, 0, 1~)	~2 \cdot 2 ^ 2 + 3 \cdot 0 ^ 2 + 5 \cdot 1 ^ 2 = 13~
~3 \rightarrow 2 \rightarrow 4~	(~2, 1, 0~)	~2 \cdot 2 ^ 2 + 3 \cdot 1 ^ 2 + 5 \cdot 0 ^ 2 = 11~
~3 \rightarrow 2 \rightarrow 1 \rightarrow 5~	(~3, 0, 1~)	~2 \cdot 3 ^ 2 + 3 \cdot 0 ^ 2 + 5 \cdot 1 ^ 2 = 23~
~4 \rightarrow 2 \rightarrow 1 \rightarrow 5~	(~2, 1, 1~)	~2 \cdot 2 ^ 2 + 3 \cdot 1 ^ 2 + 5 \cdot 1 ^ 2 = 16~

Tổng chi phí vận chuyển của các xe là ~8 + 18 + 11 + 7 + 8 + 5 + 13 + 11 + 23 + 16 = 120~.

Theo kế hoạch canh tác các năm tiếp theo:

• Trong năm thứ ~1~, các ngôi làng thứ ~1, 2, 3, 4~ sẽ lần lượt sản xuất các loại nông sản thứ ~1, 3, 1, 2, 3~. Số lượng xe và lộ trình di chuyển của các xe vẫn giống như ở trên, nhưng tổng chi phí vận chuyển của các xe là: ~7 + 13 + 10 + 7 + 7 + 8 + 22 + 10 + 28 + 25 = 137~.

• Trong năm thứ ~2~, các ngôi làng thứ ~1, 2, 3, 4~ sẽ lần lượt sản xuất các loại nông sản thứ ~1, 3, 2, 2, 3~. Số lượng xe và lộ trình di chuyển của các xe vẫn giống như ở trên, nhưng tổng chi phí vận chuyển của các xe là: ~7 + 10 + 10 + 7 + 8 + 8 + 22 + 17 + 25 + 25 = 139~.