Một giàn đèn trang trí kích thước , các hàng đánh số từ đến từ trên xuống dưới, các cột đánh số từ đên từ trái sang phải. Ô nằm giao giữa hàng và cột gọi là ô . Trên mỗi ô có một bóng đèn, mỗi bóng đèn có ba trạng thái: hoặc tắt, hoặc bật sáng màu xanh, hoặc bật sáng màu đỏ. Có ô phân biệt của giàn đèn, mỗi ô có một công tắc điều khiển. Khi tác động vào công tắc của ô thì những đèn nằm trong các ô thuộc hình chữ nhật có ô trái trên là và ô phải dưới là sẽ đổi trạng thái . Cụ thể, các đèn nằm trong các ô mà , và , sẽ thay đổi theo quy tắc: nếu đèn đang ở trạng thái tắt sẽ chuyển sang trạng thái bật sáng màu xanh, nếu đang ở trạng thái bật sáng màu xanh sẽ chuyển sang trạng thái bật sáng màu đỏ, còn nếu đèn đang ở trạng thái bật sáng màu đỏ sẽ chuyển sang trạng thái tắt. Mỗi công tắc có thể tác động nhiêu lần.
Yêu câu: Cho thông tin trạng thái ban đầu các đèn trên giàn và các công tắc. Hãy tìm cách đưa tất cả các đèn về cùng một trạng thái bật sáng màu xanh hoặc bật sáng màu đỏ với số lần tác động là ít nhât.
Dữ liệu vào:
Dòng đầu chứa ba số nguyên dương ;
Dòng thứ trong số dòng tiếp theo chứa số nguyên nhận giá trị hoặc . Số thứ mô tả trạng thái đèn ở ô là tắt, bật sáng màu xanh hoặc bật sáng màu đỏ tương ứng với các giá trị , hoặc ;
Dòng thứ trong số dòng tiếp theo chứa bốn số nguyên dương .
Các số trên cùng một dòng cách nhau bởi dấu cách.
Dữ liệu ra:
Ghi ra duy nhất một số nguyên là số lần tác động ít nhất để các đèn về cùng một trạng thái sáng màu xanh hoặc sáng màu đó, nếu không tôn tại cách tác động thì ghi số ;
Giói hạn:
Có số test ứng với số điểm của bài thỏa mãn điều kiện: ;
số test khác ứng với số điểm của bài thỏa mãn điều kiện: ;
số test còn lại ứng với số điểm của bài thỏa mãn điều kiện: .
Ví dụ:
Dữ liệu vào:
2 3 3
2 1 0
2 1 0
1 1 2 3
1 2 2 3
1 3 2 3
Dữ liệu ra:
2
Giải thích:
Trước tiên tác động vào công tắc ở ô , sau đó tác động vào công tắc ở ô , khi đó tất cả các đèn trên giàn đều sáng màu đỏ.
