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  $

----- Sample Input 1 ------ 
3

1 3

2 2

1 3

2

2 2

3 2
----- Sample Output 1 ------ 
E

E
----- explanation 1 ------ 
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.

Difficulty: MEDIUM_HARD
Tags: Preprocessing

Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
n = int(input())
L = []
M = []
N = [0] * (n + 1)
for _ in range(n):
	(a, b) = map(int, input().split())
	M.append((a, b))
	L.append(b - a + 1)
	N[a - 1] += 1
	N[b] -= 1
for i in range(1, n):
	N[i] += N[i - 1]
q = int(input())
ans = sum(L)
for _ in range(q):
	(a, b) = map(int, input().split())
	ans2 = ans - L[a - 1] - N[b - 1]
	if M[a - 1][0] <= b <= M[a - 1][1]:
		ans2 -= 1
	if ans2 % 2 == 0:
		print('E')
	else:
		print('O')


def xnor(a, b):
	if a == b:
		return 1
	return 0

def matrix_parity(r):
	p = 1
	for i in range(1, N + 1):
		p = xnor(row_parity(i), p)
	return p

def row_parity(x):
	x = x - 1
	if (r[x][1] - r[x][0] + 1) % 2 == 0:
		return 1
	else:
		return 0

def intersect_parity(x, y):
	x -= 1
	if r[x][0] <= y and r[x][1] >= y:
		return 0
	else:
		return 1

def column_parity(y):
	y -= 1
	if c[y] % 2 == 0:
		return 1
	else:
		return 0
N = int(input())
r = []
for n in range(N):
	r.append([int(x) for x in input().split()])
c = [0 for i in range(N)]
for i in range(N):
	c[r[i][0] - 1] += 1
	try:
		c[r[i][1]] -= 1
	except IndexError:
		pass
for i in range(1, N):
	c[i] = c[i] + c[i - 1]
pmatrix = matrix_parity(r)
Q = int(input())
for q in range(Q):
	(X, Y) = [int(x) for x in input().split()]
	prow = row_parity(X)
	pcolumn = column_parity(Y)
	pintersection = intersect_parity(X, Y)
	if xnor(xnor(xnor(prow, pcolumn), pintersection), pmatrix) == 1:
		print('E')
	else:
		print('O')


import sys
n = int(input())
a = list()
b = [0 for i in range(n + 2)]
a.append((0, 0))
for i in range(1, n + 1):
	line = input().split()
	a.append((int(line[0]), int(line[1])))
	b[a[i][0]] += 1
	b[a[i][1] + 1] -= 1
q = int(input())
s = 0
for i in range(1, n + 2):
	b[i] += b[i - 1]
	s += b[i]
while q:
	line = input().split()
	i = int(line[0])
	j = int(line[1])
	x = s - b[j] - (a[i][1] - a[i][0] + 1)
	if j >= a[i][0] and j <= a[i][1]:
		x -= 1
	if x % 2 == 0:
		sys.stdout.write('E\n')
	else:
		sys.stdout.write('O\n')
	q -= 1


N = int(input())
L = [0] * N
R = [0] * N
Left = [0] * N
Right = [0] * N
rowpairity = [0] * N
columnpairity = [0] * N
pairity = 0
for i in range(N):
	(a, b) = input().split(' ')
	(c, d) = (int(a) - 1, int(b) - 1)
	Left[i] = c
	Right[i] = d
	L[c] += 1
	R[d] += 1
	rowpairity[i] = (d - c + 1) % 2
	pairity = (pairity + d - c + 1) % 2
columnpairity[0] = L[0] % 2
for i in range(1, N):
	columnpairity[i] = (columnpairity[i - 1] + L[i] - R[i - 1]) % 2
Q = int(input())
for i in range(Q):
	(a, b) = input().split(' ')
	(r, c) = (int(a) - 1, int(b) - 1)
	if Left[r] <= c and c <= Right[r]:
		if (pairity - columnpairity[c] - rowpairity[r] + 1) % 2 == 0:
			print('E')
		else:
			print('O')
	elif (pairity - columnpairity[c] - rowpairity[r]) % 2 == 0:
		print('E')
	else:
		print('O')


N = int(input())
A = [0 for i in range(0, N + 1)]
ROW = [[]]
total = 0
for i in range(1, N + 1):
	(L, R) = list(map(int, input().strip().split(' ')))
	ROW += [[L, R]]
	total += R - L + 1
	A[L] += 1
	if R < N:
		A[R + 1] -= 1
total %= 2
Col = []
temp = 0
for i in range(N + 1):
	temp += A[i]
	Col += [temp % 2]
Q = int(input())
for _ in range(Q):
	(x, y) = list(map(int, input().strip().split(' ')))
	temp = 0
	(L, R) = ROW[x]
	if y >= L and y <= R:
		temp = 1
	ans = total - (R - L + 1) - Col[y] + temp
	ans %= 2
	if ans == 0:
		print('E')
	else:
		print('O')


from itertools import accumulate
n = int(input())
s = 0
rs = [0] * n
cs = [0] * (n + 1)
for i in range(n):
	(l, r) = map(int, input().split())
	l -= 1
	cs[l] += 1
	cs[r] -= 1
	rs[i] = (l, r)
	s ^= r - l
cs = list(accumulate(cs))
for _ in range(int(input())):
	(i, j) = map(int, input().split())
	i -= 1
	j -= 1
	(l, r) = rs[i]
	ans = s
	ans ^= r - l
	ans ^= 1 if l <= j < r else 0
	ans ^= cs[j]
	print('O' if ans % 2 == 1 else 'E')


read = lambda : map(int, input().split())
(n,) = read()
row = [0] * n
col = [0] * (n + 1)
segm = [None] * n
total = 0
for i in range(n):
	(l, r) = read()
	l -= 1
	segm[i] = (l, r)
	row[i] = r - l & 1
	col[l] ^= 1
	col[r] ^= 1
	total ^= r - l & 1
for i in range(1, n):
	col[i] ^= col[i - 1]
(q,) = read()
for _ in range(q):
	(r, c) = read()
	r -= 1
	c -= 1
	ret = total ^ row[r] ^ col[c] ^ (1 if segm[r][0] <= c < segm[r][1] else 0)
	print('O' if ret == 1 else 'E')