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

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, as usual, is encircled with a high and deep fence. As you know, Lara Croft has penetrated into the cemetry through the sap in the NorthWestern corner in order to find the treasures hidden in the graves. To do that, she has dug an underground passage according to the following rule: if there was an intact grave straight ahead, then Lara lengthened the passage during one night and ravaged the grave. 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. You must have already heard that she found one of the treasures. And she is going to find another one soon. However, Lara doesn't know that Dark Forces have decided to ensnare her. As soon as Lara finds the second treasure (and goes immediately to buy the usual bottle of champagne), a new alarm system (of "LaraKiller" brand) will be set off.
First of all, the all-seeing-eye tower will go online. The eye will locate Lara after some time. At once the skeleton re-animation process will be initiated in some of the ravaged graves. It takes T seconds for skeletons to revive, and Lara will certainly try to escape before these T seconds run out.
As a head programmer of the "LaraKiller" company, you are to calculate where Lara can be located at the moment of complete skeletons' revival. You should not revive unnecessary skeletons. Otherwise you'll have to kill them yourself.
It's clear that Lara will run along her underground passage not faster than 1 grave per second.


The first input line contains two numbers: N and M, 2 ≤ N,M ≤ 100 — the dimensions of the cemetry. The second line consists of the treasure grave coordinates. The third line contains Lara's coordinates at the moment the all-seeing-eye located her. The fourth line contains the number of seconds T.
Assume that the NorthWestern grave has coordinates (1, 1) and the South-Eastern — (N, M). Lara starts to dig her passage from the grave (1, 1) moving to the East, i.e. to the grave (1, 2). You may assume that T is less than 24 hours.


Output coordinates of the graves where Lara can be located T seconds after the all-seeing-eye detected her. The coordinate pair of each grave is to be output on a separate line. The numbers shall be separated with spaces. The graves shall be sorted by the distance that Lara will have to run from this grave to the cemetry entrance.


5 4
4 3
2 2
5 2
5 1
4 1
3 1
2 1
2 2
2 3
3 3
4 3
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