Piet

Piet là một ngôn ngữ lập trình bí truyền (esoteric) nổi tiếng, trong đó chương trình được biểu diễn bằng các khối điểm ảnh (pixel) nhiều màu. Trong bài này ta dùng một tập luật đơn giản hóa của Piet.

Chương trình là một ảnh chữ nhật gồm các điểm ảnh có màu hoặc màu đen. Màu của mỗi điểm ảnh là một chữ số từ $0$ đến $9$, trong đó $0$ là màu đen. Một khối là một hình chữ nhật gồm các điểm ảnh cùng màu (khác đen). Bảo đảm rằng mọi nhóm điểm ảnh cùng màu liên thông đều tạo thành khối chữ nhật. Các điểm ảnh đen có thể tạo thành hình dạng bất kỳ.

Con trỏ lệnh (IP) gồm ba thành phần:

• Con trỏ khối (BP): khối màu hiện tại (không có khái niệm điểm ảnh hiện tại bên trong khối).
• Con trỏ hướng (DP): chỉ về một trong bốn hướng trái, phải, lên, xuống.
• Bộ chọn khối (CP): chỉ về bên trái hoặc bên phải so với hướng DP; theo giá trị tuyệt đối, CP lệch so với DP $90$ độ ngược chiều kim đồng hồ (trái) hoặc thuận chiều kim đồng hồ (phải).

Ban đầu BP chỉ về khối chứa điểm ảnh góc trên bên trái, DP chỉ sang phải, CP chỉ sang trái.

Một bước biến đổi trạng thái IP như sau. Bộ thông dịch tìm cạnh xa nhất của khối hiện tại theo hướng DP. Trong các điểm ảnh tạo nên cạnh đó, chọn điểm ảnh xa nhất theo hướng CP. Sau đó BP thử di chuyển từ điểm ảnh này sang điểm ảnh kế tiếp theo hướng DP:

• Nếu điểm ảnh kế tiếp thuộc một khối có màu, khối đó trở thành khối hiện tại, DP và CP giữ nguyên.
• Nếu điểm ảnh kế tiếp là màu đen hoặc nằm ngoài chương trình, BP giữ nguyên nhưng DP và CP thay đổi: nếu CP đang chỉ sang trái thì đổi sang phải (DP giữ nguyên); nếu CP đang chỉ sang phải thì đổi sang trái và DP quay $90$ độ thuận chiều kim đồng hồ.

Bảo đảm rằng BP không bao giờ chỉ về khối đen (điểm ảnh góc trên bên trái không phải màu đen).

Cho một chương trình Piet, hãy xác định màu của khối hiện tại sau $n$ bước thông dịch.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $m$ và $n$: số dòng của ảnh và số bước thông dịch.
• $m$ dòng tiếp theo mô tả các dòng của chương trình; tất cả có cùng độ dài, gồm các ký tự chữ số $0$–$9$. Ký tự đầu tiên của dòng đầu tiên khác $0$.

Dữ liệu ra

• Màu (một chữ số) của khối hiện tại sau $n$ bước.

Ràng buộc

• $1\le m\le 50$
• $1\le n\le 5·{10}^7$
• Mỗi dòng có độ dài từ $1$ đến $50$ ký tự.

Ví dụ