Sudoku (ban đầu có tên gọi là Number Place) là một trò chơi câu đố sắp xếp chữ số dựa trên logic theo tổ hợp.

Mục tiêu của trò chơi là điền các chữ số vào một lưới (grid) ~9 \times 9~ sao cho mỗi cột, mỗi hàng, và mỗi phần trong số chín lưới con ~3 \times 3~ cấu tạo nên lưới chính (cũng gọi là "hộp" (box), "khối" (block), hoặc "khu vực" (region)) đều chứa tất cả các chữ số từ ~1~ tới ~9~.

Cơ cấu điều chỉnh câu đố cung cấp một lưới đã được hoàn thành một phần, mỗi câu dố được thiết lập tốt có một giải pháp hoàn thành duy nhất.

Với một bài toán Sudoku, một số được xem như là điền đúng vị trí khi:

• Trong hàng ngang ~9~ ô của số đó, không có số nào lặp lại số này.
• Trong hàng dọc ~9~ ô của số đó, không có số nào lặp lại số nay.
• Trong ô vuông ~3 \times 3~ của số đó, không có số nào lặp lại số nȧy.

Viết chương trình:

Input Specification

• Nhận đầu vào là một Sudoku kích thước ~9 \times 9~ với ~9~ lưới con kích thước ~3 \times 3~ và một số ~n~ cùng với tọa độ vị trí ~(i, j)~ người chơi muốn đặt ~n~ trên bàn chơi.

Output Specification

Kiểm tra xem vị trí đặt ~n~ có hợp lệ hay không.

• Nếu có, in ra màn hình Valid place.
• Ngược lại, in thông báo Invalid place.
• Nếu số ~n~ không hợp lệ, in thông báo Invalid number.

Note

• Trong bàn chơi Sudoku được nhập vào, nếu vị trí ~(i, j)~ trong bàn chơi chưa có bất cứ số nào thì vị trí lưu giá trị ~0~. Tọa độ ~(i, j)~ được đánh số từ ~1~.

Sample Cases

Input #1:

0 2 0 3 1 6 5 7 8
8 6 7 5 0 4 1 9 0
0 1 0 8 9 0 2 4 6
9 3 0 7 0 5 6 2 4
6 0 2 9 4 1 0 3 5
7 4 5 2 6 3 9 8 1
3 5 4 0 7 0 8 1 9
1 0 8 4 0 9 3 0 2
2 9 6 1 3 8 4 5 7
4 1 1

Output #1:

Valid place.