The Great Wall#2084
King Louis has two sons who hate each other. Fearing that after his death the country will be destroyed by terrible wars, he decides to split his realm into two parts, each ruled by one son. He seats them in cities and , and wishes to build the minimal number of wall segments so that there is no path from city to city .
The kingdom can be represented as a rectangle of size m \times n. Some cells contain mountains, which are impassable, while others are freely traversable. Additionally, some cells are suitable for wall construction, while on others building is not possible.
Movement across the country is allowed only between side-adjacent cells, provided neither contains a mountain or a wall segment.
The first line contains the integers and (1 \leq m, n \leq 50). The second line contains the integers and , where 0 \leq k, l, k + l \leq m \cdot n - 2. Here, is the number of mountain cells, and is the number of cells where walls can be built. Mountains cannot be used for wall construction. The next lines contain the coordinates of cells with mountains, x_i and y_i. The following lines contain the coordinates of cells where walls can be built, x_j and y_j. The last two lines contain the coordinates of the cities (x_A and y_A) and (x_B and y_B). All these k+l+2 cells are different. It is guaranteed that 1 \leq x_i, x_j, x_A, x_B \leq m and 1 \leq y_i, y_j, y_A, y_B \leq n.
Print the minimum number of wall segments to be built in the first line. In the next lines, print one possible set of cell coordinates for wall placement.
If it is impossible to achieve this, print only in the output.
Example 1