The 8 puzzle is a very well-known sliding block puzzle involving a ~3 \times 3~, each containing a single tile (numbered from ~1~ to ~8~), except for one square. A move consists of sliding a single tile adjacent (up, down, left, or right) to the empty square, into the empty square location. For example, consider the following grid (with ~0~ being the empty square):

0 1 2
3 4 5
6 7 8

The following is the grid after a single move (moving the 1 piece to the left):

1 0 2
3 4 5
6 7 8

It's easy to see that this game can be generalized for an ~N \times M~ grid.

A tournament has been organized where ~K~ players, numbered from ~1~ to ~K~, will compete against each other in ~Q~ games, using an ~N \times M~ grid. At the beginning of the tournament, each player is assigned a starting grid configuration, which they are required to use for the entire tournament. However, asking all the players to solve the same puzzle multiple times would be too easy. Instead, the tournament organizers will ask the players to match a target grid configuration, for each game.

Both the initial grid configurations and target grid configurations are generated by starting from the board layout in the first diagram above, and selecting a valid move uniformly at random up to ~1\,000~ times.

Assuming each player plays optimally, you want to know who will win each game. The winner of the game is the player that makes the least number of moves. In the event of a tie, the player with the smallest player number wins.

Constraints

Subtask 1 [5%]

~N = 2,\quad M = 2,\quad K = 2,\quad Q = 1~

Subtask 2 [10%]

~N = 2,\quad M = 3,\quad 2 \le K \le 10,\quad Q = 300~

Subtask 3 [10%]

~N = 3,\quad M = 3,\quad 2 \le K \le 10,\quad Q = 10^4~

Subtask 4 [50%]

~N = 3,\quad M = 3,\quad 2 \le K \le 10^4,\quad Q = 10^5~

Subtask 5 [25%]

~N = 3,\quad M = 4,\quad K = 2,\quad Q = 1~

Input Specification

The first line contains 4 integers, ~N~, ~M~, ~K~, and ~Q~.

The next ~K \times N~ lines describe the starting grid configurations that each player must use.

Each player's grid will consist of ~N~ lines, each with ~M~ integers. Each integer will be between ~0~ and ~(N \times M) - 1~, representing the number of the tile, or an empty square if the number is ~0~.

The next ~Q \times N~ lines describe the target grid configuration for each game.

Each target grid will consist of ~N~ lines, each with ~M~ integers. Each integer will be between ~0~ and ~(N \times M) - 1~, representing the number of the tile, or an empty square if the number is ~0~.

Output Specification

Output ~Q~ lines, each containing two integers. The first integer on the ~i^{th}~ line is the player number of the winner of the ~i^{th}~ game, assuming each player plays optimally to make as few moves as possible. In the event of a tie, the player with the smallest player number wins. The second integer on the ~i^{th}~ line is the number of moves taken by the winner of the ~i^{th}~ game to reach the target configuration.

Sample Input (not in any test cases)

2 2 2 2
3 2
1 0
2 0
3 1
0 1
2 3
3 2
1 0

Sample Output

2 3
1 0

Sample Explanation

Please note that the sample input does not satisfy any of the constraints for any of the subtasks. It will not appear in any of the test cases.

For the first game:

Player 1's optimal sequence:

3 2  ->  3 2  ->  0 2  ->  2 0  ->  2 1  ->  2 1  ->  0 1
1 0      0 1      3 1      3 1      3 0      0 3      2 3

Player 2's optimal sequence:

2 0  ->  2 1  ->  2 1  ->  0 1
3 1      3 0      0 3      2 3

Thus, player 2 wins with 3 moves.

For the second game, player 1 wins without having to make any moves.