Carambole (1) P65201

Carom (or carambole) billiards is one of the existing modalities of billiard games. In this case we wish to solve a simplified version of this game. There is a player and two balls (white and red) on a cloth-covered, pocketless table. The red ball is placed inside the table, without touching any corner or border, and the white ball in one of the corners (see figure).

The white ball starts a traversal following the diagonal and changes direction (following the other diagonal) when reaching a table side. If it arrives to a corner (where only one diagonal exists) the ball stops.

For the simulation we assume that we have a table of dimension n× m and that the white ball traversal finishes whenever:

1. touches a corner of the table,
2. touches the red ball,
3. touches four sides of the table,

The player makes a carambole when the white ball traversal ends touching the red ball after touching exactly three sides of the table.

Your task is to write a program that reads the configuration of a Carom billiard table and determines whether the player has made a carambole. The program must also enumerate the positions where the white ball touches the sides of the table and must show the final configuration of the table.

Your program must use the following definitions:

typedef vector< vector <char> > Table;

struct Ball {

   int x_pre, y_pre;   // Previous position of the ball

   int x_cur, y_cur;   // Current position of the ball

   int x_nex, y_nex;   // Next position of the ball

};

Your program must also design, implement and use the following function:

void move_until_touching (Table& t, Ball& b);

which, given a table t and a ball b, moves the ball b within t in the direction and orientation defined by the ball’s current and next position. The ball must stop when touching the red ball (if it does) or one side or one corner of the table. After finalizing the execution of the function, b must hold the stop position as actual position and both previous and last positions correctly settled.

Take into account that when the ball touches a corner the next position must be this corner. The positions visited by the ball while moving on t must be marked in t.

Input

The input is formed by several descriptions of a configuration of a Carom billiard. Each one is formed by two integers n, m ≥ 2 corresponding to the number of rows and columns in the matrix representing the table, respectively. Followed by a sequence of four integers x₁, y₁, x₂, y₂ giving the initial positions of the two balls.

The ball at position (x₁, y₁) is the white ball and it is always placed in one of the corners (i.e., one of (0,0), (0, m − 1), (n − 1, 0) or (n − 1, m − 1)). The ball at position (x₂,y₂) is the red ball it is allways placed inside the table (i.e., 0<x₂<n−1 and 0<y₂< m−1).

Output

For each input configuration table you have to write the coordinates of the positions where the white ball touches the sides. Yo have also to indicate if the player makes carambole or not as well as to show the trajectory followed by the white ball. Please follow the format specified in the examples.