0x56

Một ngày đẹp trời, lớp chuyên Tin quyết định xả stress bằng một buổi dạo chơi ở công viên và hoạt động được mong chờ nhất chính là đạp vịt. Giữa khung cảnh hồ nước thơ mộng, Peace và Matcha Latte đang cùng nhau trên một chiếc thuyền thiên nga 🦢.

Thay vì tận hưởng không khí lãng mạn, Peace với bộ não của một "dân code", lại trải một tấm bản đồ của khu hồ ra và đưa cho Matcha Latte một thử thách: "Tớ thấy khu hồ này có ~n~ địa điểm check-in rất đẹp, tớ đã đánh số chúng từ ~1~ đến ~n~. Địa điểm số ~1~ là bến tàu của chúng ta và địa điểm cuối cùng - số ~n~ là điểm hẹn bí mật, nơi mà cả lớp tập trung ăn kem và uống matcha latte. Giờ cậu hãy thử làm kiến trúc sư quy hoạch các tuyến đường đi cho thuyền vịt nhé".

Peace chỉ vào con số ~k~ khổng lồ ghi trên góc tấm bản đồ và giải thích:

"Đây là chỉ số lãng mạn mà tớ muốn tấm bản đồ của chúng ta đạt được. Chỉ số này được tính bằng tổng số các hành trình khả dĩ khác nhau để đi từ bến tàu (điểm ~1~) đến điểm hẹn bí mật (điểm ~n~)".

Matcha Latte ngơ ngác hỏi: "Hành trình khả dĩ là sao?"

Peace mỉm cười: "Một hành trình là một chuỗi các địa điểm nối tiếp nhau. Ví dụ, ~1 \rightarrow 2 \rightarrow 5 \rightarrow n~ là một hành trình. Điều quan trọng là, để không ai bị lạc và đạp vịt vòng vòng mãi mãi, các tuyến đường cậu vạch ra phải là đường một chiều và không được tạo ra bất kỳ chu trình nào. Cậu có thể tạo ra bao nhiêu tuyến đường tùy thích, miễn là bản đồ cuối cùng có đúng chỉ số lãng mạn là ~k~"

Peace nói thêm với vẻ mặt đầy thách thức: "Tất nhiên, đó là nếu việc này khả thi với chỉ ~n~ địa điểm. Nếu không thể nào tạo ra bản đồ với đúng chỉ số ~k~, cậu chỉ cần nói là MATCHA thôi. Còn nếu làm được, hãy cho tớ xem bản đồ của cậu nhé!"

Nhiệm vụ của bạn là hãy giúp Matcha Latte xác định xem yêu cầu của Peace có thực hiện được không. Nếu được, hãy đưa ra một bản đồ quy hoạch (một đồ thị có hướng, không chu trình - DAG) thỏa mãn.

Input

• Gồm một dòng duy nhất chứa hai số nguyên dương ~n~ và ~k~ ~(2 \leq n \leq 50, 1 \leq k \leq 10^{18})~ lần lượt là số địa điểm trong công viên và chỉ số lãng mạn mong muốn.

Output

• In ra MATCHA ở dòng đầu tiên nếu không tồn tại cách quy hoạch nào thỏa mãn yêu cầu.
• Nếu ngược lại, in ra LATTE ở dòng đầu tiên. Sau đó, ở ~n~ dòng tiếp theo, in ra một ma trận kề ~n \times n~ của bản đồ bất kì thỏa mãn mà bạn thiết kế. Nếu tại dòng ~i~, cột ~j~ có giá trị là ~1~, điều đó có nghĩa là có một tuyến đường một chiều từ địa điểm ~i~ đến địa điểm ~j~. Ngược lại, giá trị ~0~ có nghĩa là không có.

Example input 1

4 3

Example output 1

LATTE
0 1 1 0
0 0 1 1
0 0 0 1
0 0 0 0

Note 1

Yêu cầu của Huy là khả thi. Với bản đồ được cung cấp, có đúng ~3~ hành trình khả dĩ từ bến tàu ~(1)~ đến điểm hẹn ~(4)~, khớp với ~k = 3~.

1. ~1 \rightarrow 2 \rightarrow 3 \rightarrow 4~
2. ~1 \rightarrow 2 \rightarrow 4~
3. ~1 \rightarrow 3 \rightarrow 4~