Đây là một bài toán interactive.

Bạn sẽ thực hiện ~t~ ván khác nhau tại trò chơi dò mìn.

Mỗi ván đấu, bạn sẽ chơi trên một lưới ô vuông gồm ~n~ hàng và ~m~ cột, mỗi ô sẽ ở trong trạng thái có mìn hoặc không có mìn (lưu ý rằng kích thước lưới ô vuông và trạng thái các ô có thể khác nhau qua các ván đấu). Nhưng bạn không biết trạng thái của các ô là thế nào cả, trừ việc có tổng cộng ~k~ ô có mìn.

Bạn có thể dò một ô bất kỳ để biết nó có mìn hay không. Nếu nó có mìn, bạn sẽ thêm ~1~ điểm phạt (trước mỗi trò chơi, bạn có ~0~ điểm phạt); nếu nó không có mìn, bạn sẽ biết được số ô có mìn trong ~8~ ô vuông gần với nó nhất.

Mục tiêu cuối cùng của bạn là phải tìm được vị trí tất cả các ô có mìn, sao cho điểm phạt là bé nhất có thể.

Để làm điều này, bạn sẽ nộp một lời giải cho máy chấm. Quá trình kiểm tra lời giải của bạn diễn ra như sau:

• Lời giải của bạn có thể dò ô tại hàng thứ ~x~ - cột thứ ~y~ bằng cách lần lượt in ra ~x~ và ~y~ trên một dòng.

  • Nếu ô này có mìn, máy chấm sẽ in ra ~-1~.

  • Nếu không, máy chấm sẽ in ra số ô có mìn trong ~8~ ô vuông gần với ô tại hàng thứ ~x~-cột thứ ~y~ nhất.

• Lời giải của bạn có thể tuyên bố rằng đã tìm được tất cả các ô có mìn bằng cách in ra hai số ~0~ trên một dòng, và ~k~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên dương là chỉ số hàng và chỉ số cột của các ô có mìn.

  • Nếu danh sách các ô có mìn là đúng, số điểm bạn nhận được phụ thuộc vào số lượng số ~-1~ mà máy chấm in ra, kích cỡ trò chơi, và số lượng mìn.

  • Ngược lại, bạn sẽ nhận được ~0~ điểm.

• Trước khi tuyên bố rằng đã tìm được tất cả các ô có mìn, bạn có thể tiếp tục dò các ô bất cứ số lần nào.

Input

Ban đầu, bạn được nhận một số nguyên dương duy nhất là ~t~ ~(t=5)~. Mỗi lượt chơi bắt đầu như sau:

• Máy chấm lần lượt in ra ~3~ số nguyên dương là ~n~, ~m~, và ~k~ ~(5 \leq n \leq m \leq 100; 1 \leq 4k \leq nm)~.

• Sau mỗi lần dò của bạn, bạn sẽ nhận thêm một số nguyên là câu trả lời của máy chấm.

• Nếu bạn đã tuyên bố rằng đã tìm được tất cả các ô có mìn, lượt chơi hiện tại kết thúc và lượt chơi tiếp theo (nếu có) bắt đầu.

Dữ liệu đầu vào đảm bảo các ô có mìn không thay đổi trong quá trình tương tác, không thay đổi qua các lần nộp, được gieo với phân phối ngẫu nhiên và đồng xác suất.

Máy chấm đảm bảo trạng thái có mìn hay không có mìn của các ô trong một ván đấu không thay đổi.

Output

Mỗi lượt chơi bắt đầu như sau:

• Lời giải nhận được ~3~ số nguyên dương là ~n~, ~m~, và ~k~ từ máy chấm.

• Lời giải có thể dò một ô trên lưới ô vuông, hoặc tuyên bố rằng đã tìm được tất cả các ô có mìn.

• Nếu bạn chưa tuyên bố rằng đã tìm được tất cả các ô có mìn, bạn có thể tiếp tục dò những ô khác.

Việc không in ra kết quả theo định dạng trên có thể gây ra lỗi và ảnh hưởng đến điểm số cuối cùng của bạn.

Interaction

Scoring

Công thức tính điểm của bạn tại mỗi lượt chơi sẽ được ẩn. Bạn được biết một số tính chất về nó như sau:

• Đảm bảo rằng tồn tại ~k~ không âm sao cho nếu bạn dò không quá ~k~ ô có mìn thì bạn nhận điểm tuyệt đối.

• Đảm bảo rằng dò ít ô có mìn hơn sẽ làm điểm cao hơn (nếu điểm chưa là điểm tuyệt đối).

• Đảm bảo rằng công thức chỉ phụ thuộc vào ~n~, ~m~, và ~k~.

Điểm của một bộ dữ liệu là điểm thấp nhất của các lượt chơi.

Notes

Giải thích ví dụ:

Nếu bạn sử dụng C++, hãy thêm lệnh 'cout<<endl' hoặc 'cout.flush()' sau mỗi truy vấn để máy chấm có thể nhận thông tin từ bạn.