Query over Matrix

All submissions for this problem are available.
Read problems statements in Mandarin Chinese , Russian and Vietnamese as well.
Read problems statements in Mandarin Chinese , Russian and Vietnamese
There is a N*N square matrix. You have been given N specifications, one per row of the matrix. The i^{th} specifications is represented by a pair of integers L[i] and R[i], denoting that all element belonging to columns between L[i] and R[i] (both inclusive) in row i are 1, while the rest of the elements of the i^{th} row are 0.
Now you will be given an integer Q, followed by Q operations: Each query is described by two integers x and y, which asks what will be the parity of the sum of the matrix if the x^{th} row and the y^{th} column are removed from the matrix.
Input
 First line of the input contains an integer N, followed by N lines: each containing a pair of integers. i^{th} pair of integers denotes the value of L[i] and R[i].
 The next line contains the value of Q, and the following Q lines contain the queries.
Output
Q lines, each containing a single character "E" or "O" (no quotes needed), indicating whether the sum is even or odd.
Constraints
Subtask #1: 20 points
 1 ≤ N,Q ≤ 1000, 1 ≤ L[i] ≤ R[i] ≤ N,1 ≤ x,y ≤ N
Subtask #2: 80 points
 1 ≤ N,Q ≤ 10^{5}, 1 ≤ L[i] ≤ R[i] ≤ N, 1 ≤ x,y ≤ N
Example
Input: 3 1 3 2 2 1 3 2 2 2 3 2 Output: E E
Explanation
The given array is:
1 1 1
0 1 0
1 1 1
It's easy to see that the sum is even in both the queries.
Author:  amitpandeykgp 
Tester:  pushkarmishra 
Editorial  http://discuss.codechef.com/problems/QMAXTRIX 
Tags  amitpandeykgp, implementation, ltime30, precomputation 
Date Added:  3112015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions