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).



The first line of the input consists two integers m and n - the dimentions 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".


Process the commands and print whenever necessary.


Input Constraints:



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



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

x1<=x2 y1<=y2


Sample Input:

5 5
C 2 1 4 1 1
D 3 1
D 3 3
C 2 1 5 2 0
D 3 1


Sample Output:




hide comments
Simes: 2022-03-15 16:16:20

For the benefit of any future solvers, the commands are actually in "C y1 x1 y2 x2 d" and "D y x" format. Y then X, not X then Y as stated in the problem description.

nikunjsoni: 2017-07-05 07:34:28

Brute force also passed
Constraints not that tough

hodobox: 2016-04-21 23:29:47

Doesn't have to be solved using 2D BIT, as the amount of queries is sufficiently low. Good for practicing it though

Lehar: 2015-12-25 16:09:39

The i/o specification should be mentioned clearly :/

alpha coder: 2015-12-12 22:03:03

0.06 using 2d BIT ! that feel when you implement 2d bit :)

zzzoom: 2015-11-13 00:03:28

learned a lot

nh10: 2015-05-28 20:02:11

How to do using bit??

Sunil: 2015-04-30 08:14:25

a (m *log n) approach update with lazy propagation gives TLE, requires (log m * log n)

Samuel Nacache: 2014-11-30 02:51:13

Although not necessary, it's a good problem for 2D segment tree practice :)

appy: 2014-10-22 17:51:59

is wind is blowing from north to south in anticlockwise direction in 1st case, then the whole column of that will be in south or not ?? and also what about the (3,2) it still E or it will change to south too...??

Added by:cegprakash
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: BF GOSU