| Author: | I. Ludov | Time limit: | 1 sec | |
| Input file: | input.txt | Memory limit: | 64 Mb | |
| Output file: | output.txt |
The Gridland is a small country located on a beautiful hilly landscape. It is well known for its achievements in the fields of nanotechnology and car industry.
The country has many cities, located in the nodes of W × H grid with square cells. All roads between cities go straight along the lines of the grid in either north-south or east-west direction and have the same length.
A young scientist Vasya Reshetkin developed a new hi-tech car powered by nuclear batteries. The car is very energy-efficient: while going uphill, the car consumes a fixed amount of energy per unit of distance, and while going downhill it stops the engine, consuming no energy at all. That means that the amount of energy required to travel along the fixed route from A to B and then back from B to A depends only on the distance, and not on the inclination profile of the road.
Thus if the car requires a units of energy to move from a city to its neighbor, then moving back will require L − a units, where L is the same for all cities. To simplify maintenance, each battery was designed to store exactly L units of energy.
Unfortunately, prolonged storage of half-used batteries may lead to nuclear contamination of the environment, so it is important that the batteries are always used fully.
Your country is known for achievements in computer programming. So you have been given a job to write a program that plans a route from city A to city B such that it will use exactly L × k units of energy for some integer k. This route may not be the shortest one, but this is a price Gridland citizens are willing to pay for environment preservation.
First line of input file contains integers L W H — battery capacity, width and height of city grid respectively.
Second line contains integers rA cA rB cB — row and column of city A and row and column of city B respectively. Rows span from west to east in order of increasing column numbers. Columns span from north to south in order of increasing row numbers. All numbering is zero-based.
Next H − 1 lines contain 2 * W − 1 integers e1 s1… eW − 1 sW − 1 sW, where ei is the energy required to move from i-th city in the row to its eastern neighbor, and si — energy to move to its southern neighbor.
Last line contains W − 1 integers ei — energy required to move from the i-th city in the southernmost row to its eastern neighbor.
Output file must contain a single line with the string of symbols "N", "S", "E", "W", describing a route from city A to city B which requires integer amount of batteries of capacity L. It there is more than one answer, output any of them not exceeding 3(H + W)L in length. If there is no answer, output a single symbol "X".
| No. | Input file (input.txt) |
Output file (output.txt) |
|---|---|---|
| 1 | |
|