Giải bài trực tuyến

Nuga là một cô bé thông minh, rất thích phiêu lưu. Cô thường lang thang trong vũ trụ bằng con tàu siêu tốc AlphaX. Một hôm, con tàu của Nuga đi lạc vào một hành tinh lạ.

Hành tinh có dạng một hình vuông khổng lồ, có cạnh là N (năm ánh sáng). Do sức hút của hành tinh quá lớn, không một vật thể nào, kể cả ánh sáng có thể thoát ra ngoài được, chính vì thế mà hàng mấy tỉ năm nay, không ai phát hiện ra sự tồn tại của hành tinh này.

Trong lúc thăm dò, Nuga phát hiện ra hàng triệu “viên đá” hình cầu to bằng cả trái đất nằm rải rác khắp hành tinh, mỗi viên đá mang một năng lượng riêng. Khi quét bản đồ hành tinh lên máy tính, Nuga thấy một điều rất đặc biệt, đó là nếu chia hành tinh thành N hàng, N cột, đánh số từ 1 đến N theo chiều từ trái sang phải và từ trên xuống dưới thì mỗi viên đá nằm gọn trong một ô vuông.

Nhờ phân tích các số liệu, Nuga đã biết được bí quyết “mở cửa” Hành Tinh Đá để thoát ra ngoài là phải kết nối được sức mạnh của K viên đá thần kỳ. Tuy nhiên, Nuga phải nhanh chóng xác định vị trí của chúng.

Công việc này hóa ra lại phức tạp hơn Nuga tưởng tượng, bởi hành tinh quá rộng lớn. Nghĩ rằng sắp xếp lại các viên đá có thể giúp tìm kiếm nhanh hơn, Nuga đã sắp xếp các viên đá trên mỗi hàng theo thứ tự năng lượng tăng dần, rồi sau đó lại tiếp tục sắp xếp các viên đá trên mỗi cột theo thứ tự năng lượng tăng dần.

Đến đây thì vừa mệt vừa đói, Nuga chưa tìm được hướng đi tiếp theo. Bạn hãy giúp Nuga với!

Input

• Dòng đầu ghi số 2 nguyên dương: N là độ dài 1 cạnh của hành tinh, và K là số lượng viên đá thần kỳ.
• N dòng tiếp theo, mỗi dòng ghi N số nguyên. Các số nguyên khác nhau đôi một. Số nguyên ở dòng thứ I, cột thứ J thể hiện năng lượng của viên đá tại vị trí (I, J) trên bản đồ mà Nuga đã sắp xếp.
• K dòng sau, mỗi dòng ghi 1 số nguyên là năng lượng của 1 viên đá thần kỳ cần tìm. Dữ liệu đảm bảo tất cả các viên đá thần đều có trên hành tinh.

Output

• Gồm K dòng, mỗi dòng ghi 2 số nguyên I, J thể hiện vị trí của viên đá thần kỳ tương ứng với năng lượng đã cho.

Hạn chế

• Năng lượng của mỗi viên đá nằm trong khoảng [0, 2^31 - 1]
• N ≤ 1000, K ≤ 10000.

Ví dụ

Input:
2 2
1 2
3 4
3
1


Output:
2 1
1 1