Sudoku là một trò chơi trí tuệ dành cho ~1~ người, được chơi trên bảng ~9 \times 9~, chia thành ~9~ hình vuông nhỏ ~3 \times 3~.

Ban đầu có một số ô của bảng chứa các chữ số ~1~ đến ~9~. Những ô còn lại rỗng.

Nhiệm vụ của người chơi Sudoku là điền các chữ số từ ~1~ đến ~9~ vào bảng, sao cho trong mỗi hàng, mỗi cột, và trong ~9~ ô vuông ~3 \times 3~ của bảng có đủ tất cả các chữ số từ ~1~ đến ~9~ (nói cách khác, mỗi chữ số từ ~1~ đến ~9~ xuất hiện đúng một lần trong mỗi hàng, mỗi cột, và trong ~9~ ô vuông ~3 \times 3)~.

Nhiệm vụ của bạn trong bài toán này hơi khác một chút: thay vì điền tiếp các chữ số vào bảng Sudoku, bạn cần tạo ra ~1~ bảng Sudoku hợp lệ (nghĩa là mỗi hàng, mỗi cột, và ~9~ ô vuông ~3 \times 3~ đều có đủ các chữ số từ ~1~ đến ~9)~.

Input

Bài này không có input

Output

In ra đúng ~9~ dòng, mỗi dòng gồm ~9~ ký tự là ~9~ chữ số của dòng tương ứng.

Giới hạn

• Nếu bạn đưa ra một bảng Sudoku không hợp lệ, bạn được ~0~ điểm.

• Ngược lại, điểm của bạn được tính như sau:

  • Gọi ô ở hàng ~u~, cột ~v~ là ô ~(u~, ~v)~.
  • Với mỗi số ~i~ từ ~1~ đến ~9~, ta định nghĩa ~sum(i) = \sum(|u-x| \times |v - y|)~ với tất cả các cặp ô ~(u, v)~ và ~(x, y)~ chứa số ~i~.
  • Điểm của bạn được tính theo công thức: $$\min(\left(max\left(0, \sum_{i = 1}^9 (sum(i) \times i) - 17000\right), 1062 \right)$$

• Điểm càng cao càng tốt.

Sample Output

683459172
241673859
759182364
492836715
536217498
817594236
928361547
174925683
365748921

Note

Với output mẫu, ~sum(1) = 398~, ~sum(2) = 404~, ..., ~sum(9) = 374~. $$\sum_{i=1}^{9}(sum(i) \times i) = 17056$$ Điểm bạn nhận được là ~56~.