ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural Championship 2005 Round II

About     Problems     Submit solution     Judge status     Standings
Contest is over

E. LaraKiller

Time limit: 1.0 second
Memory limit: 64 MB
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 (rT, cT). Now she is returning home to drink champagne. But Dark Forces have decided to ensnare her. As soon as Lara will reach the grave (rL, cL), 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 (rL, cL).
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.

Input

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 rT and cT that are the treasure grave's coordinates. The third line contains integers rL and cL that are Lara's coordinates at the moment the alarm system turns on. 1 ≤ rT, rLN; 1 ≤ cT, cLM. It is guaranteed that the passage from the grave (1, 1) to the grave (rTcT) goes through the grave (rLcL).
The fourth line contains an integer T that is a time of skeletons' revival, in seconds (0 ≤ T ≤ 27000).

Output

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.

Sample

inputoutput
5 4
4 3
2 2
5
5 2
5 1
4 1
3 1
2 1
2 2
2 3
3 3
4 3

Notes

In the picture you can see the graves where Lara can hide.
Problem illustration
Problem Author: Stanislav Vasilyev
Problem Source: IX Collegiate Students Urals Programming Contest. Yekaterinburg, April 19-24, 2005
To submit the solution for this problem go to the Problem set: 1364. LaraKiller