<PREV Problem:
NEXT>
Solved by 53 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Prisoner

Time limit = 2 second(s)

(THIS IS DRAFT)

Prisoner Nickolay Borsov escaped from prison and now he is in the forest. And forest is very dense. One can use only paths going through it.

Paths are equally distanced (1 kilometer) straight line going from the south to the north, and from the west to the east.

Forest is rectangular.

Police wants to catch him and make catching barriers, which are straight segment with endpoints ant paths intersections.

Nickolay should find the way from point A to point B (where his frinds are waining for him with helicopter) not intersecting barriers.

Mafia found you and give you task to program algorithm that finds the shortest path. Price is your life.

Input

N M K
ax ay bx by
sx1 sy1 fx1 fy2
sx2 sy2 fx2 fy2
....
sxK syK fxK fyK

N — is WEST-EAST length, M — is SOUTH-NORTH length. K is the number of barriers.

The firts line contains N, M, and K. The second line contains coordinates of the points A and B.

K lines after the first two lines contain descriptions of barriers.

Coordinates are from [0, N] (x-coordinate) and [0, M] (y-coordinate).

Output Two lines. The first conains shortest path length. The second — description of the path — word consisting of letters N, S, W, E, i.e. instruction describing how Nickolay should go through the forest from A to B.

Output "NO SOLUTION" if there is now path from A to B.

Input#1
4 5 3
3 1 3 4
2 2 4 3
0 4 1 4
2 4 2 5
Output#1
7
WWNNEEN
Input#2
4 5 3
3 1 3 4
2 2 4 3
0 4 1 4
2 2 2 3
Output#2
NO SOLUTION

Author:
Andrey Ulanov, Personal Programming MIPT Contest, 7 October 2007
4 October 2007

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 220ms

SW soft NIX
ID = 54.161.108.158