Farmer John cho rằng ngôi nhà của mình cần được trang trí thêm. Khi ghé thăm cửa hàng đồ sứ địa phương, ông tìm thấy một bức tượng bò bằng thủy tinh tinh xảo và quyết định mua nó vì biết rằng nó sẽ vừa vặn hoàn hảo trên bệ lò sưởi nhà mình.

Hình dạng của bức tượng bò được mô tả bằng một lưới ký tự \(N \times N\) như dưới đây (\(3 \leq N \leq 8\)), trong đó các ký tự # là một phần của bức tượng còn các ký tự . thì không.

...............
...............
...............
#..#...........
####...........
############...
.##.#########..
....#######.##.
....##...##....
....##...##....
...............
...............
...............
...............
...............

Không may, ngay trước khi FJ có thể mua hàng, một con bò đực chạy xuyên qua cửa hàng và làm vỡ không chỉ bức tượng của FJ mà còn nhiều đồ vật bằng thủy tinh khác trên các kệ! Bức tượng của FJ vỡ thành 2 mảnh, rồi nhanh chóng lẫn vào tổng cộng \(K\) mảnh nằm trên sàn (\(3 \leq K \leq 10\)). Mỗi mảnh trong số \(K\) mảnh được mô tả bằng một lưới ký tự \(N \times N\), giống như bức tượng ban đầu.

Hãy giúp FJ xác định hai mảnh nào trong số \(K\) mảnh là những mảnh ông cần dán lại để sửa bức tượng bị vỡ. May mắn thay, khi hai mảnh tượng của ông rơi xuống sàn, chúng không bị xoay hay lật. Vì vậy, để lắp ráp lại, FJ chỉ cần có thể tịnh tiến các mảnh theo chiều ngang và/hoặc chiều dọc rồi chồng chúng lên nhau. Nếu chọn đúng hai mảnh, ông phải có thể làm điều này theo cách khôi phục chính xác bức tượng ban đầu, sao cho mỗi ký tự # trong bức tượng ban đầu được biểu diễn trong đúng một trong hai mảnh (nghĩa là sau khi được tịnh tiến và chồng lên nhau, hai mảnh không được có chung bất kỳ ký tự # nào và hợp của chúng phải tạo thành chính xác hình dạng ban đầu).

FJ có thể tịnh tiến một mảnh theo chiều dọc và/hoặc chiều ngang một số ký tự tùy ý, nhưng không được tịnh tiến xa đến mức bất kỳ ký tự # nào của mảnh nằm ngoài lưới \(N \times N\) ban đầu. Hình dạng của mỗi mảnh không nhất thiết chỉ gồm một vùng ký tự # "liên thông"; tuy nhiên, nếu một mảnh gồm nhiều cụm ký tự # rời nhau thì tất cả các cụm phải được tịnh tiến cùng một khoảng khi toàn bộ mảnh được tịnh tiến.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), tiếp theo là \(K\). \(N\) dòng tiếp theo cung cấp lưới ký tự mô tả bức tượng ban đầu của FJ. \(KN\) dòng tiếp theo cung cấp \(K\) lưới ký tự mô tả \(K\) mảnh mà FJ tìm thấy trên sàn.

Dữ liệu ra

In một dòng chứa hai số nguyên cách nhau bởi dấu cách, mỗi số nằm trong khoảng \(1 \ldots K\), biểu thị chỉ số của hai mảnh thuộc bức tượng của FJ. Luôn tồn tại đúng một lời giải. Hai số được in ra phải theo thứ tự tăng dần.

Ví dụ

4 3
####
#..#
#.##
....
.#..
.#..
##..
....
####
##..
#..#
####
....
.###
.#..
.#..

1 3

Nguồn

USACO 2016 US Open Contest, Bronze - Bull in a China Shop: https://usaco.org/index.php?page=viewproblem2&cpid=640

Tác giả: Brian Dean.