Kurukshetra OPC 2013

Problem Statement:

Wind vane is an instrument for showing the direction of the wind.

Dream city is in the shape of a matrix of dimensions mxn. To monitor the direction of the wind in the city, wind vanes are placed in every unit cell of the city. According to the direction of the wind, these wind vanes turn themselves. Lets assume that there are only 4 directions North, East, West and South denoted by (‘N’, ’E’, ’W’, ’S’). We know the initial direction of the wind vanes.

We denote the direction of change of wind by 0 (clockwise) and 1 (anti-clockwise)

Function “Change(x1, y1, x2, y2, direction)”, changes the direction of the vanes in the sub-matrix (from x1, y1 to x2, y2) in the specified ‘direction’

(for example if the initial state of a cell is ‘N’ and the direction is clockwise, then the cell changes to ‘E’)

The ‘Change’ may occur any time. We need to know the direction of the wind at any unit cell at any instant.

Direction (x, y) should print the direction of the vane at the cell (x, y).

Input:

The first line of the input consists two integers m and n - the dimensions of the city. Then follows the description of the matrix which denotes the direction of the vanes. The next line contains an integer c, the number of commands to process. Each command can be either of the format "C x1 y1 x2 y2 d" or "D x y".

Output:

Process the commands and print whenever necessary.

Input Constraints:

1<=m<=1000

1<=n<=1000

each character in the matrix is one among {'N','E','W', and 'S'}

1<=c<=10000

1<=x1,y1,x2,y2,x,y<=1000

d= 0(clockwise) or 1(anti-clockwise)

x1<=x2 y1<=y2

Sample Input:

5 5
ESWNE
NWWWN
EEESE
SSWSN
SNWEN
5
C 2 1 4 1 1
D 3 1
D 3 3
C 2 1 5 2 0
D 3 1

Sample Output:

N

E

E