Bạn đang phát triển một trò chơi mô phỏng nơi hai thế lực giao chiến trên bản đồ lưới 2 chiều kích thước $H \times W$.

Mỗi ô trên lưới có thể được biểu diễn bằng cặp tọa độ $(y, x)$. Các ô ở hàng đầu tiên được biểu diễn lần lượt từ trái sang phải là $(0,0), (0,1), \dots, (0, W-1)$, các ô ở hàng thứ hai là $(1,0), (1,1), \dots, (1, W-1)$. Các ô khác cũng được biểu diễn tọa độ theo cách tương tự cho đến hàng thứ $H$. Các ô nằm phía trên, dưới, trái, phải của một ô được gọi là các ô 'kề' với ô đó.

Bản đồ bao gồm nhiều loại địa hình khác nhau, mỗi loại có một chỉ số 'độ hiểm trở' nhất định. Ngoài ra, trên bản đồ có nhiều đơn vị quân được bố trí không chồng lấp lên nhau, mỗi đơn vị thuộc về một trong hai thế lực đang giao chiến. Mỗi đơn vị có thể di chuyển từ vị trí hiện tại sang các ô kề nếu không ra ngoài bản đồ. Khi di chuyển, đơn vị sẽ tiêu tốn lượng thể lực bằng với độ hiểm trở của địa hình ô đó. Một số địa hình quá hiểm trở khiến việc di chuyển vào là không thể. Nếu hai đơn vị thuộc hai thế lực khác nhau đứng ở các ô kề nhau, chúng đang ở trạng thái giao chiến.

Tất cả các đơn vị đều có thể lực vô hạn vì đã được chuẩn bị đầy đủ khẩu phần ăn chiến đấu. Tuy nhiên, mỗi đơn vị bị giới hạn tổng lượng thể lực tối đa có thể tiêu tốn trong một lần 'đột kích', gọi là 'khả năng di chuyển' của đơn vị đó. Đột kích là một hành động chiến thuật trong đó đơn vị đang chiến đấu di chuyển nhanh chóng đến một mục tiêu tương đối gần bằng cách đi qua một hoặc nhiều ô. Đột kích chỉ có thể thực hiện nếu không có đơn vị nào khác tại điểm mục tiêu. Nếu gặp đơn vị cùng thế lực trong khi đột kích, đơn vị có thể đi xuyên qua, nhưng nếu gặp đơn vị khác thế lực, đơn vị phải dừng lại ngay tại vị trí kề với đơn vị đó vì giao chiến sẽ xảy ra. Tuy nhiên, nếu đơn vị được chọn đã ở trạng thái giao chiến, nó có thể đột kích để thoát khỏi giao chiến.

Bạn đã tạo một con bot tự động chọn ngẫu nhiên các đơn vị và ra lệnh đột kích để kiểm tra xem trò chơi có lỗi hay không. Con bot này đôi khi đưa ra các lệnh đột kích không thể thực hiện được. Nếu có đơn vị khác tại điểm mục tiêu, điểm mục tiêu là địa hình không thể đi vào, hoặc không tồn tại đường đi đến điểm mục tiêu do giới hạn khả năng di chuyển, thì lệnh đó không thể thực hiện. Nếu trò chơi không có lỗi, các lệnh này phải bị bỏ qua.

Bây giờ là lúc kiểm tra xem có lỗi hay không. Hãy viết chương trình xuất ra tọa độ của mỗi đơn vị sau khi tất cả các lệnh của bot được xử lý theo trình tự thời gian.

Dữ liệu vào

Dòng đầu tiên chứa số loại địa hình $N$, chiều cao bản đồ $H$, và chiều rộng bản đồ $W$ cách nhau bởi dấu cách. ($1 \le N \le 9, 2 \le H, W \le 500$)

Tiếp theo là $H$ dòng, mỗi dòng chứa $W$ số nguyên cách nhau bởi dấu cách, biểu thị số hiệu loại địa hình của từng ô từ trái sang phải, mỗi số từ $1$ đến $N$.

Dòng tiếp theo chứa $N$ số nguyên $r_1, r_2, \dots, r_N$ ($-1 \le r_i \le 4, r_i \neq 0$) cách nhau bởi dấu cách. Nếu $r_i$ là $-1$, nghĩa là địa hình thứ $i$ quá hiểm trở không thể đi vào, ngược lại $r_i$ là độ hiểm trở của địa hình thứ $i$.

Dòng tiếp theo chứa số lượng đơn vị $M$. ($1 \le M \le H \times W / 4$)

Tiếp theo là $M$ dòng, mỗi dòng chứa bốn số nguyên $m, t, a, b$ cách nhau bởi dấu cách, biểu thị khả năng di chuyển, thế lực, tọa độ $y$ và tọa độ $x$ của đơn vị đó (theo thứ tự từ đơn vị 1 đến $M$). ($1 \le m \le 20, 0 \le t \le 1, 0 \le a < H, 0 \le b < W$)

Mỗi ô chứa tối đa một đơn vị, và không có đơn vị nào được đặt tại các ô có địa hình không thể đi vào.

Dòng tiếp theo chứa số lượng lệnh đột kích $K$. ($1 \le K \le 10\,000$)

Tiếp theo là $K$ dòng, mỗi dòng chứa ba số nguyên $u, a, b$ cách nhau bởi dấu cách, biểu thị lệnh đột kích đơn vị $u$ đến $(a, b)$. ($1 \le u \le M, 0 \le a < H, 0 \le b < W$)

Dữ liệu ra

Xuất ra vị trí của các đơn vị sau khi tất cả các lệnh đột kích được xử lý trên $M$ dòng. Nếu đơn vị $i$ nằm tại $(a_i, b_i)$, hãy xuất ra hai số nguyên $a_i, b_i$ cách nhau bởi dấu cách trên dòng thứ $i$.

Ví dụ

Ví dụ 1

3 5 5
1 1 3 3 2
3 3 3 1 2
1 1 1 2 1
2 2 1 1 1
1 1 1 1 3
1 3 -1
2
7 0 2 0
4 1 3 3
3
1 1 3
2 4 4
1 4 3

Ví dụ 1

4 3
3 3

Ghi chú

Đối với lệnh đột kích đầu tiên, nếu không xét đến đơn vị thế lực đối địch, đơn vị có thể di chuyển theo lộ trình $(2,0) \to (2,1) \to (2,2) \to (2,3) \to (1,3)$. Tuy nhiên, do có đơn vị thế lực đối địch tại $(3,3)$, giao chiến xảy ra tại $(2,3)$ nên không thể đến được $(1,3)$, và vì không có lộ trình vòng tránh nào khác để không xảy ra giao chiến, lệnh này không thể thực hiện và bị bỏ qua.

Lệnh đột kích thứ hai bị bỏ qua vì vị trí mục tiêu là địa hình không thể đi vào.

Lệnh đột kích thứ ba có thể thực hiện bằng cách di chuyển theo lộ trình $(2,0) \to (3,0) \to (4,0) \to (4,1) \to (4,2) \to (4,3)$, tiêu tốn $7$ thể lực. Đây là giá trị không vượt quá khả năng di chuyển của đơn vị nên lệnh này hợp lệ.

Do đó, sau khi tất cả các lệnh được xử lý, đơn vị 1 nằm tại $(4,3)$ theo lệnh cuối cùng và đơn vị 2 vẫn nằm tại vị trí ban đầu.