Đây là một bài chỉ xuất kết quả (output-only).

Năm 2018, Kỳ thi Olympic Tin học Quốc tế sẽ được tổ chức tại Nhật Bản. Để chào mừng sự kiện này, ban tổ chức IOI dự định tạo một tác phẩm nghệ thuật có "thiết kế hơi kỳ lạ" và trang trí nó tại địa điểm thi. Ban tổ chức đã nhờ Công ty TNHH JOI (Just Odd Inventions) thiết kế tác phẩm. Các nhà thiết kế của JOI đề xuất như sau:

• Tác phẩm được tạo trên một bảng hình chữ nhật gồm \(H \times W\) ô. Ta sẽ lát bảng bằng \(N\) viên gạch và các viên gạch không chồng lên nhau.
• Viên gạch thứ \(i\) (\(1 \le i \le N\)) có kích thước \(1 \times 1\) hoặc \(1 \times 2\), và có màu \(C_i\).
• Có thể xoay một viên gạch kích thước \(1 \times 2\) để dùng nó như một viên gạch kích thước \(2 \times 1\).

Họ cũng đã đề xuất các loại gạch dùng cho tác phẩm, nhưng lại chưa đề xuất cách lát gạch trên bảng, vốn là phần quan trọng nhất của thiết kế. Vì các thiết kế của JOI luôn đẹp, ban tổ chức quyết định giữ nguyên các loại gạch do JOI đề xuất và tự tìm cách lát sao cho độ đẹp của tác phẩm lớn nhất.

Độ đẹp được tính như sau:

• Với mỗi cạnh chung của hai ô thuộc hai viên gạch có màu lần lượt là \(j\) và \(k\), cạnh đó đóng góp \(A_{j,k}\) điểm.
• Độ đẹp của tác phẩm là tổng điểm của tất cả các cạnh như vậy.

Nếu hai viên gạch kích thước \(1 \times 2\) tiếp xúc nhau qua cạnh của hai cặp ô, điểm của cả hai cạnh đều được tính riêng.

Hãy xác định một cách lát các viên gạch lên bảng sao cho độ đẹp lớn nhất có thể.

Dữ liệu vào

Bài có năm nhóm. Mỗi nhóm tương ứng với một tệp dữ liệu vào công khai. Bạn cần tải đủ năm tệp 01.txt, 02.txt, 03.txt, 04.txt, 05.txt trong phần tệp đính kèm của đề bài và tạo một tệp kết quả tương ứng cho mỗi tệp dữ liệu vào.

Mỗi tệp dữ liệu vào có định dạng sau:

• Dòng đầu chứa bốn số nguyên \(H\), \(W\), \(K\), \(N\), lần lượt cho biết bảng có \(H \times W\) ô, có \(K\) màu gạch và có \(N\) viên gạch.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) (\(1 \le i \le N\)) chứa hai số nguyên \(S_i\), \(C_i\). Viên gạch thứ \(i\) có kích thước \(1 \times S_i\) và màu \(C_i\).
• Trong \(K\) dòng tiếp theo, dòng thứ \(j\) (\(1 \le j \le K\)) chứa \(K\) số nguyên \(A_{j,1}, A_{j,2}, \ldots, A_{j,K}\). Khi hai viên gạch màu \(j\) và \(k\) có chung một cạnh, cạnh đó đóng góp \(A_{j,k}\) điểm.

Dữ liệu ra

Với mỗi tệp dữ liệu vào, hãy nộp một tệp kết quả gồm đúng \(N\) dòng. Dòng thứ \(i\) (\(1 \le i \le N\)) mô tả vị trí của viên gạch thứ \(i\):

• Nếu \(S_i = 1\), dòng thứ \(i\) chứa hai số nguyên \(R_i\), \(C_i'\). Viên gạch thứ \(i\) được đặt tại ô ở hàng \(R_i\) tính từ trên xuống và cột \(C_i'\) tính từ trái sang.
• Nếu \(S_i = 2\), dòng thứ \(i\) chứa bốn số nguyên \(R_i\), \(C_i'\), \(R_i'\), \(C_i''\). Viên gạch thứ \(i\) phủ hai ô \((R_i, C_i')\) và \((R_i', C_i'')\).

Một tệp kết quả hợp lệ phải thỏa mãn tất cả các điều kiện sau:

• Mọi tọa độ đều nằm trên bảng.
• Với viên gạch kích thước \(1 \times 2\), hai ô được chỉ ra phải khác nhau và có chung một cạnh.
• Không có hai viên gạch nào phủ cùng một ô.
• Mọi ô của bảng đều được phủ bởi đúng một viên gạch.
• Dòng thứ \(i\) phải mô tả đúng viên gạch thứ \(i\) và có đúng số lượng số nguyên theo kích thước của viên gạch đó.

Nếu tệp kết quả không hợp lệ, nhóm tương ứng nhận \(0\) điểm.

Ràng buộc

Mọi tệp dữ liệu vào thỏa mãn:

• \(1 \le H \le 100\).
• \(1 \le W \le 100\).
• \(1 \le K \le 100\).
• \(1 \le N \le 10\,000\).
• \(1 \le S_i \le 2\) (\(1 \le i \le N\)).
• \(1 \le C_i \le K\) (\(1 \le i \le N\)).

• \(0 \le A_{j,k} \le 1\,000\) (\(1 \le j,k \le K\)).
• \(A_{j,k} = A_{k,j}\) (\(1 \le j,k \le K\)).

Phân nhóm

Với ý nghĩa của \(X\) và \(Y\), xem phần Chấm điểm.

Chấm điểm

Mỗi nhóm gồm đúng một tệp dữ liệu vào và có tối đa \(20\) điểm. Gọi \(B\) là độ đẹp của cách lát trong tệp kết quả tương ứng.

• Nếu cách lát không hợp lệ, điểm của nhóm là \(0\).
• Nếu cách lát hợp lệ và \(B < X\), điểm của nhóm là \(0\).
• Nếu cách lát hợp lệ và \(X \le B < Y\), điểm của nhóm là

Tương đương, vì điểm là số nguyên, giá trị trên bằng

• Nếu cách lát hợp lệ và \(B \ge Y\), điểm của nhóm là \(20\).

Tổng điểm của bài là tổng điểm của năm nhóm, tối đa \(100\) điểm.

Ví dụ

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

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