Hãy tưởng tượng bạn đang lạc vào một mê cung công nghệ kỳ bí được tạo nên từ một lưới ô vuông kích thước ~N \times N~. Mỗi ô trong mê cung chứa một con số – chỉ có thể là ~0~ hoặc ~1~ – và mỗi con số ấy ẩn chứa một ý nghĩa riêng. Nhiệm vụ của bạn là bắt đầu hành trình từ ô ~(1,1)~ và tìm lối đi đến ô ~(N,N)~ sao cho theo đường đi của bạn, các số thu thập được tạo thành một xâu nhị phân có giá trị lớn nhất. Quy tắc di chuyển khá đơn giản: từ ô ~(i,j)~ bạn chỉ có thể tiến sang ô bên phải ~(i,j+1)~ hoặc ô bên dưới ~(i+1,j)~. Tuy nhiên, việc chọn lựa con đường đúng đắn lại chính là chìa khóa để bạn mở ra "kho báu" của mê cung, đó chính là xâu nhị phân tối ưu. Hãy dùng trí tuệ và sự tinh ý của mình để khám phá con đường dẫn đến xâu nhị phân lớn nhất, bởi chỉ có như vậy bạn mới có thể chứng minh khả năng "đọc hiểu" mê cung đầy ẩn số này!

Input

• Dòng đầu tiên chứa một số nguyên dương ~N~ ~(N \leq 10^3)~.
• Tiếp theo, có ~N~ dòng, mỗi dòng chứa ~N~ số ~(0~ hoặc ~1)~, biểu diễn ma trận của mê cung.

Output

• In ra xâu nhị phân lớn nhất được hình thành từ đường đi từ ô ~(1,1)~ đến ô ~(N,N)~.

Sample Input

4
1 0 0 1
0 1 1 0
1 0 0 1
0 1 1 1

Sample Output

1011011

Notes

• Một trong những đường đi tạo ra xâu nhị phân lớn nhất là: ~(1,1) → (2,1) → (2,2) → (2,3) → (3,3) → (4,3) → (4,4)~, cho xâu nhị phân ~1011011~.