The shortest path of two knights

Translate each of the two knights from their starting positions to their respective target squares using the minimum total number of moves. The two knights must not occupy the same square at the same time.

Input

The input begins with the coordinates of the first knight, followed by the coordinates of the second knight. Next, the coordinates of the destination squares for each knight are provided.

Output

Output the sequence of moves for the knights, with each move on a separate line. Each line should start with the knight's number (1 or 2), followed by the coordinates of the square to which the knight moves, separated by a space. You should provide any one of the possible optimal solutions.

Examples