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

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~.