Task:

Two knights are staying in an 8*8 chessboard.

Swap their positions.

These two knights can’t stay in one cell simultaneously.

It is known that at the start the first knight makes a move, and then both go by turns.

Input:

The first line contains coordinates (x1, y1) of the cell the first knight stands in.

The second line contains coordinates (x2, y2) of the cell the second knight stands in.

Output:

The first line should contain the minimal number of turns k.

The next k lines should contain three numbers each – firstly – the number of the knight making his move (either 1 or 2), secondly – the x coordinate of the move, thirdly – the y coordinate of the move.

If it’s impossible to swap the knights, write -1.

Example:

Input


3 2

1 1

Output

6

1 2 4

2 2 3

1 3 2

2 4 4

1 1 1

2 3 2

Input

8 6

8 1

Output
6

1 7 4

2 7 3

1 6 2

2 6 5

1 8 1

2 8 6