Đi trên ma trận

Trò chơi "Đi trên ma trận" diễn ra trên một bảng $n\times m$ gồm các số nguyên không âm $a_{i,j}$. Người chơi xuất phát tại ô $(1,1)$ với điểm số ban đầu bằng $a_{1,1}$, và mỗi bước chỉ được đi sang phải hoặc đi xuống, tức là từ $(x,y)$ sang $(x,y+1)$ hoặc $(x+1,y)$, miễn là không ra khỏi bảng. Mỗi khi bước vào một ô mới, điểm số hiện tại được thay bằng phép AND bit giữa điểm số đó và giá trị của ô vừa bước vào. Mục tiêu là tới ô $(n,m)$ với điểm số lớn nhất có thể.

Bob giải bài toán này bằng quy hoạch động như sau, với $f_{i,j}$ là điểm số tốt nhất mà thuật toán của Bob tính được cho ô $(i,j)$:

$$f_{1,1}=a_{1,1}$$

$$f_{i,j}=max(f_{i-1,j}<mrow><mi>\&</mi></mrow>a_{i,j},f_{i,j-1}<mrow><mi>\&</mi></mrow>a_{i,j})$$

(chỉ lấy những số hạng tương ứng với ô nằm trong bảng), rồi in ra $f_{n,m}$.

Thuật toán này không đúng: $f_{n,m}$ có thể nhỏ hơn điểm số lớn nhất thực sự.

Cho số nguyên không âm $k$, hãy dựng một bảng $a$ sao cho:

• $1\le n,m\le 500$;
• $0\le a_{i,j}\le 3·{10}^5$ với mọi $1\le i\le n$, $1\le j\le m$;
• hiệu giữa điểm số lớn nhất thực sự và giá trị $f_{n,m}$ mà thuật toán của Bob in ra đúng bằng $k$.

Có thể chứng minh rằng với mọi $k$ thỏa mãn $0\le k\le {10}^5$ luôn tồn tại một bảng như vậy. Nếu có nhiều bảng hợp lệ, in ra bảng nào cũng được.

Dữ liệu vào

Một dòng duy nhất chứa số nguyên $k$.

Dữ liệu ra

• Dòng đầu chứa hai số nguyên $n$ và $m$: kích thước bảng.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa $m$ số nguyên $a_{i,1},a_{i,2},\dots ,a_{i,m}$.

Ràng buộc

• $0\le k\le {10}^5$

Ví dụ