Trong thời gian rảnh rỗi ở nhà học online, Phát đã nghĩ ra một trò chơi để giải trí trong lúc "afk". Trò chơi gồm một bảng kích thước ~r \times c~, ô nằm ở hàng ~i~, cột ~j~ là ~(i, j)~. Ban đầu, mọi ô trên bảng đều bằng ~0~.

Phát cũng thiết kế thêm các nút bấm ở mỗi hàng sao cho khi bấm nút ở hàng ~i~ thì sẽ làm tăng tất cả các ô ở hàng ~i~ lên ~1~ đơn vị. Tương tự, các nút bấm ở mỗi cột cũng được Phát thiết kế để tăng các ô trên cột đó lên ~1~ đơn vị. Tuy nhiên, mỗi ô trên bảng chỉ có thể hiển thị được các số từ ~0~ đến ~k-1~ nên nếu giá trị của một ô tăng lên ~k~ thì giá trị ô đó lập tức trở về ~0~. (Xem ví dụ bên dưới với ~r=2~, ~c=3~ và ~k=3~ để hiểu rõ hơn)

Sau một lúc bấm nút, Phát đã tìm ra bảng yêu thích của cậu. Cậu lập tức đi lấy giấy bút để ghi chép lại nó. Tuy nhiên trong lúc cậu đi khỏi, Hiệp đã đến và xáo mất bảng của cậu. Phát rất muốn khôi phục lại bảng nhưng cậu chỉ nhớ được giá trị của ~q~ ô.

Trong lúc đang tìm lại bảng yêu thích của mình thì Phát nhận được thông báo đến trường học trực tiếp. Thế nhưng chưa kịp vui mừng vì được gặp thầy cô, bạn bè thì Phát nhận được một tin sét đánh: "Thầy sẽ chấm vở ghi để lấy điểm".

Phát hoảng hốt vì những ngày học online Phát chỉ mở điện thoại nghe bài giảng cho vui rồi nằm ngủ chứ không ghi chép gì cả. Thời gian thì rất gấp mà Phát lại muốn tìm ra bảng đó càng sớm càng tốt. Nhưng trong cái khó ló cái khôn, Phát nhận ra mình có thể đem bài toán này vào contest Bedao Hay Không? Hay Hay để nhờ các bạn giải hộ trong lúc Phát đi chép bài.

Các bạn hãy giúp Phát tìm ra cách nhanh nhất (tổng số lần bấm nút ít nhất) để khôi phục lại bảng yêu thích của cậu từ bảng ban đầu với giá trị tất cả các ô bằng ~0~ (và học bài nhớ ghi chép bài đầy đủ, đừng như Phát nha :))))

Input

• Dòng đầu tiên chứa bốn số nguyên ~r~, ~c~, ~q~, ~k~ (~1 \le r, c \le 10^5~, ~1 \le q \le \min(r \cdot c, 3 \cdot 10^5)~, ~2 \le k \le 10^9~).
• Dòng thứ ~i~ trong ~q~ dòng tiếp theo chứa ba số nguyên ~x_i~, ~y_i~, ~v_i~ thể hiện Phát nhớ được giá trị của ô ~(x_i, y_i)~ là ~v_i~ (~1\le x_i \le r~, ~1 \le y_i \le c~, ~0 \le v_i < k~, ~x_i \ne x_j~ hoặc ~y_i \ne y_j~ với mọi ~i \ne j~).

Output

Nếu Phát nhớ nhầm, in ra ~-1~. Ngược lại, in ra ba dòng:

• Dòng đầu tiên in ra một số nguyên là số lần bấm nút ít nhất Phát cần để khôi phục lại bảng.
• Dòng thứ hai in ra ~r~ số nguyên, số thứ ~i~ là ~row_i~ - số lần bấm nút ở hàng ~i~. (~0 \le row_i < 2^{31}~)
• Dòng thứ ba in ra ~c~ số nguyên, số thứ ~j~ là ~col_j~ - số lần bấm nút ở cột ~j~. (~0 \le col_j < 2^{31}~)

Nếu có nhiều hơn một phương án, bạn chỉ cần in ra một phương án bất kì.

Subtask

• Subtask 1 (20% số điểm): ~r \cdot c=q~, ~k = 2~
• Subtask 2 (30% số điểm): ~k \le 500~
• Subtask 3 (50% số điểm): Không có ràng buộc gì thêm

Sample Input 1

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

Sample Output 1

5
1 2
0 0 2

Sample Input 2

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

Sample Output 2

8
1 1 1
1 2 2

Sample Input 3

2 2 4 4
1 1 0
1 2 1
2 1 2
2 2 0

Sample Output 3

-1