River Crossing

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

M wolves and N dogs, where M <= N, need to cross a river from its west bank to the east bank using a boat which can hold at most two individuals. Safety constraint: the number of dogs, unless it is zero, is never less than of wolves on either bank or on the boat. General constraint: the boat needs to carry at least one individual on its way to the east bank or back to the west bank. Is it possible to cross the river without the dogs being eaten? If yes, how can we move them? Give one legal moving sequence.

This problem can be modeled by using simply the information of the occupants on the west bank, and the position of the boat. Let us use (X, Y, P)-triples to denote different states in the process of moving, where X Y and P are the numbers of wolves and dogs on the west bank and the position (west W or east E) of the boat at beginning of after a legal move, respectively. For example, the initial state is (M, N, W) and the final state is (0, 0, E). A safety state (m, n, P) for this problem will be n >= m, unless n = 0, and (N - n) >= (M - m), unless N - n = 0 (i.e., the number of dogs on either the west bank or the east bank is never less than that of the wolves at any time).

Write a program given pairs of the beginning numbers of wolves and dogs (stored in the file river.dat) will output results, separately. Each result is either a legal moving sequence, an ordered transition from the initial safe state (M, N, W) to the final state (0, 0, E), if there exists a solution, or the message \'Impossible.\' if no any solution exists. Meanwhile, a circular (or useless) moving process, i.e., from a state to a state itself after zero or several moves (transitions), is not allowed to be included in a legal moving sequence.

For example, let M = 2 and N = 2. One legal moving sequence is

(2, 2, W) -> (0, 2, E) -> (1, 2, W) -> (1, 0, E) -> (2, 0, W) -> (0, 0, E).

Input

 The input data format in the input file looks like this:

w1 d1
w2 d2
w3 d3

where w1 d1, w2 d2, and w3 d3 are the beginning numbers (integers) of wolves and dogs in the different lines. There is one space between each of the w1 d1, w2 d2 and w2 d3 pairs.

Output

 The format of output for a legal moving sequence is a set of an ordered states listed line by line. For example, the output of the aforementioned example is

(2, 2, W)
(0, 2, E)
(1, 2, W)
(1, 0, E)
(2, 0, W)
(0, 0, E)

One blank line is required for separating each of the output results. If there is no sequence of legal moves then output signle line containg Impossible.
\"\"

Sample Input


				

Sample Output


				

Hint

 

Source