IITWPC4F - Gopu and the Grid Problem

no tags 

Gopu is interested in the integer co-ordinates of the X-Y plane (0 <= x, y <= 100000). Each integer coordinate contain a lamp, initially all the lamps are in off mode. Flipping a lamp means switching it on if it is in off mode and vice versa. Maggu will ask Gopu 3 type of queries.

  • Type 1: x l r, meaning: flip all the lamps whose x-coordinate are between l and r (both inclusive) irrespective of the y coordinate.
  • Type 2: y l r, meaning: flip all the lamps whose y-coordinate are between l and r (both inclusive) irrespective of the x coordinate.
  • Type 3: q x y X Y, meaning: count the number of lamps which are in 'on mode' (say this number be A) and 'off mode' (say this number be B) in the region where x-coordinate is between x and X (both inclusive) and y-coordinate is between y and Y (both inclusive).

Input

First line contains Q-number of queries that Maggu will ask to Gopu. (Q <= 10^5)

Then there will be Q lines each containing a query of one of the three type described above.

Output

For each query of 3rd type you need to output a line containing one integer A.

Example<

Input:
3
x 0 1
y 1 2
q 0 0 2 2

Output:
4

hide comments
gaurav117: 2015-12-26 12:31:54

TLE -> due to brute force
WA ->missed long long in the final answer
but satisfaction in the end :)

Jacob Plachta: 2014-02-04 00:37:08

Where's the bound on Q?

ans: ---> updated, Thank you

Last edit: 2014-02-04 00:37:30

Added by:praveen123
Date:2014-01-31
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64