CSES - HIIT Open 2017 - Impatience
  • Time limit: 2.00 s
  • Memory limit: 512 MB

Impatience is a one-person game played on an infinitely large 2-dimensional grid. Each grid cell is either empty or it contains one pebble. We refer to grid cells with coordinates (r,c), where r is the row (numbered from top to bottom) and c is the column (numbered from left to right).

You are given two shapes, A and B, that show the positions of the pebbles. In the beginning, you place all pebbles according to shape A, with the top left corner in cell (1,1). Then you can perform a sequence of valid rotations in which you move one pebble to a new position. You win if you find a sequence of rotations so that your final configuration looks like shape B (possibly shifted horizontally and vertically, but not rotated or mirrored).

A valid rotation is defined as follows. Let r_1 and r_2 be two adjacent rows (i.e., |r_1-r_2| = 1) and let c_1 and c_2 be two adjacent columns (i.e., |c_1-c_2| = 1). Now assume that:

  • (r_1,c_1) contains a pebble
  • (r_2,c_2) is empty
  • exactly one of (r_1,c_2) and (r_2,c_1) contains a pebble.

Then we can move a pebble from (r_1,c_1) to (r_2,c_2); such a move is denoted by (r_1,c_1) \to (r_2,c_2). See the figure below for an example of inputs and a sequence of 3 valid rotations that wins the game.

Note that you are free to use both negative and positive coordinates. You can freely step outside the boundaries of the images A and B.

Input

As input, you will receive two shapes. Each shape is encoded as follows:

  • One line with two numbers n and m: the height and the width of the shape.
  • n lines, with m characters on each line. The characters are either 0 or 1, indicating an empty slot or a slot with a pebble, respectively.

The shapes do not have any holes (starting from any empty slot, you can reach another empty slot by a sequence of moves up/down/left/right through empty slots).

Output

If there is no way to win the game, output just -1.

Otherwise, output a sequence of valid rotations that wins the game, encoded as follows. First, output one line which contains just one number k, the number of rotations. Then, output k lines of the form "r_1 c_1 r_2 c_2", which indicates a rotation (r_1,c_1) \to (r_2,c_2).

You can use at most 200000 rotations in your output.

Limits

  • 1 \le n \le 15
  • 1 \le m \le 15
  • The number of pebbles in each shape is between 1 and 100.

Example 1

The following example corresponds to the above illustration.

Input:

3 3
001
111
100
2 4
1111
0010

Output:

3
1 3 2 4
2 2 3 3
3 1 2 2

Example 2

Input:

2 5
00000
11000
3 3
011
000
000

Output:

0

Example 3

Input:

3 13
0101010101110
0111010100100
0101010100100
1 1
1

Output:

-1

Example 4

Input:

1 3
111
3 2
01
01
10

Output:

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