Perimeter Patrol Bearing Log

A security patrol unit walks along the outer boundary of a rectangular compound that has been mapped onto a grid with corners at (0,0) and (width-1, height-1). The unit starts stationed at (0,0) facing East, and it only ever moves along the perimeter of the rectangle, one grid unit at a time, in a fixed counterclockwise loop:

• East along the bottom edge from (0,0) to (width-1,0)
• North along the right edge from (width-1,0) to (width-1,height-1)
• West along the top edge from (width-1,height-1) to (0,height-1)
• South along the left edge from (0,height-1) back to (0,0)

and then the loop repeats indefinitely.

You will receive a sequence of advance orders. Each order tells the unit to move forward some number of grid units along this loop (continuing smoothly through corners, changing facing as needed). After each order, report the unit's resulting coordinates and the direction it is now facing. Note that whenever the unit returns to (0,0) after having moved at all, it is treated as still facing South (the direction it was walking when it arrived there) rather than East -- it only faces East again once it has actually advanced past (0,0) into the bottom edge.

Input format

Line 1 contains two integers width and height. Line 2 contains a single integer q, the number of advance orders. Each of the next q lines contains one integer steps, the number of grid units to advance for that order.

Output format

Print q lines. The i-th line contains the unit's coordinates and facing direction after applying the first i orders in sequence, formatted as x y dir where dir is one of North, East, South, West.

Constraints

• 2 <= width, height <= 1000
• 1 <= q <= 20000
• 1 <= steps <= 10^9

3 2
3
2
1
4

2 0 East
2 1 North
1 0 East

2 3
2
5
7

0 1 South
0 0 South