A cemetery has a rectangular shape with N rows of graves and M graves in each row. The cemetry is encircled with a high fence. As you know, Lara Croft has penetrated into the cemetry through the sap in the North-Western corner in order to find the hidden treasure. To do that, she has dug a passage under the cemetery according to the following rule:

1. If there was an intact grave straight ahead, then Lara lengthened the passage and ravaged this grave.
2. If there was a cemetry fence or a ravaged grave in the way, then Lara turned 90 degrees right and continued with her questionable affairs.

Lara has just found the treasure in the grave (r_T, c_T). Now she is returning home to drink champagne. But Dark Forces have decided to ensnare her. As soon as Lara will reach the grave (r_L, c_L), a new alarm system of "LaraKiller" brand will turn on. It will revive skeletons in some of the ravaged graves. All these skeletons will be revived at the same moment, T seconds later.

Lara realizes that the alarm system turns on. She will try to escape the cemetery (if she will have enough time) or to hide in a ravaged grave. Lara can run along her underground passage not faster than one grave per second in the direction of the exit or backwards. So before these T seconds run out she can hide in any ravaged grave at a distance not more than T from (r_L, c_L).

You are a head programmer of "LaraKiller". You don't want to revive unnecessary skeletons, so you need to find all the ravaged graves where Lara can be located at the moment of skeletons' revival.

The first line contains integers N and M, that are the dimensions of the cemetery (2 ≤ N, M ≤ 100). The North-Western grave has coordinates (1, 1) and the South-Eastern one has coordinates (N, M). Lara starts to dig her passage from the grave (1, 1) moving to the East, i.e. to the grave (1, 2).

The second line contains integers r_T and c_T that are the treasure grave's coordinates. The third line contains integers r_L and c_L that are Lara's coordinates at the moment the alarm system turns on. 1 ≤ r_T, r_L ≤ N; 1 ≤ c_T, c_L ≤ M. It is guaranteed that the passage from the grave (1, 1) to the grave (r_T, c_T) goes through the grave (r_L, c_L).

The fourth line contains an integer T that is a time of skeletons' revival, in seconds (0 ≤ T ≤ 27000).

Output coordinates of the graves where Lara can be located T seconds after the alarm system will turn on. The coordinate pair of each grave is to be output in a separate line. The graves should be output in order Lara ravaged them.

In the picture you can see the graves where Lara can hide.