You are given a grid of size N x M consisting of '.' (empty), 'W' (white) or 'B' (black) cells. We follow the convention that the top left corner is the position (1,1) and bottom right corner is (N,M). 
From every '.' cell (i, j), a ray is shot towards the right. If the ray reaches a 'B' cell, it loses it's strength fully and stops there. When a ray
reaches a 'W' cell, it's strength drops drastically so that the  ray stops when it reaches a second 'W' cell. That is, if there is no 'B'
cell in between, a ray can cross at most one 'W' cell, and it will stop when it reaches the second 'W' cell. It passes unchanged through  any '.' cell. If it reaches a boundary cell (ie. (i,M), for some i), it stops there.
Let L(i, j) be length travelled by the ray starting from the cell (i, j). If (i,j) is 'W' or 'B', no ray starts from here, and hence L(i,j) is defined to be 0. If a ray starts from (i,j) and stops at (i,k), then the distance travelled by this ray is k-j+1. i.e, inclusive of both starting and ending cells.
For the given grid your task is to find the sum of L(i, j) over all 1 <= i <= N and 1 <= j <= M.  
The description of the grid is given as follows: In addition to N and M, you are given the number of 'W' cells (w) and the number of 'B' cells (b)
and you are given the locations of these w + b cells.  (The other cells contain '.')

-----Constraints:-----
For all testcases,
- 1 <= N, M <= 10^6. 
- 0 <= w,b <= 10^5
Subtask 1: 15%
It is guaranteed that 1 <= N,M <= 500
Subtask 2: 25%
It is guaranteed that 1 <= N,M <= 2000
Subtask 3: 60%
No additional guarantees.

-----Input format:-----
- There is only one line of input which contains 4 + 2w + 2b space separated integers. The first four integers are N, M, w and b. 
- The next 2*w integers denote the cells which contains a 'W': x1 y1 x2 y2 .. xw yw. These denote that (xi,yi) contains 'W'.
- The next 2*b integers denote the cells which contains a 'B': x1 y1 x2 y2 .. xb yb. These denote that (xi,yi) contains 'B'.
- The cells which are not in the input have to be assumed to be '.' 

-----Output format:-----
Output a single integer which is the sum of L(i,j) over all 1 <= i <= N and 1 <= j <= M.

-----Sample Input 1:-----
4 4 5 2 1 3 2 1 3 2 3 3 4 3 1 4 2 3

-----Sample Output 1:-----
22

-----Explanation:-----
The grid is:
. . W B
W . B .
. W W .
. . W .

L(i,j) for each cell is:
4 3 0 0
0 2 0 1
3 0 0 1
4 3 0 1

Therefore, the total is 22.

-----Note:-----
As the answer might be large, please use 64 bit integers (long long int in C/C++ and long in Java) instead of 32 bit int.

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
from operator import itemgetter
inp = list(map(int, input().split()))
(n, m, w, b) = inp[:4]
stops = []
for i in range(w):
	stops.append((inp[4 + 2 * i] - 1, inp[5 + 2 * i] - 1, 'w'))
for i in range(b):
	stops.append((inp[4 + 2 * w + 2 * i] - 1, inp[5 + 2 * w + 2 * i] - 1, 'b'))
stops.sort(key=itemgetter(1))
stops.sort(key=itemgetter(0))
counter = 0
stop_rows = [[] for _ in range(n)]
for stop in stops:
	stop_rows[stop[0]].append(stop[1:])
for row in stop_rows:
	idx = 0
	for i in range(len(row)):
		if idx == row[i][0]:
			idx += 1
		elif row[i][1] == 'w':
			if i < len(row) - 1:
				num = row[i + 1][0] - idx + 1
				counter += (num * (num + 1) >> 1) - 1
				idx = row[i][0] + 1
				num = row[i + 1][0] - row[i][0] + 1
				counter -= (num * (num + 1) >> 1) - 1
			else:
				num = m - idx
				counter += (num * (num + 1) >> 1) - 1
				idx = row[i][0] + 1
				num = m - row[i][0]
				counter -= (num * (num + 1) >> 1) - 1
		else:
			num = row[i][0] - idx + 1
			counter += (num * (num + 1) >> 1) - 1
			idx = row[i][0] + 1
	num = m - idx
	counter += num * (num + 1) >> 1
print(counter)


inputs = list(map(int, input().split()))
N = inputs[0]
M = inputs[1]
W = inputs[2]
B = inputs[3]
list1 = [['.'] * M for i in range(N)]
for i in range(4, 2 * W + 4, 2):
	list1[inputs[i] - 1][inputs[i + 1] - 1] = 'W'
for j in range(2 * W + 4, len(inputs), 2):
	list1[inputs[j] - 1][inputs[j + 1] - 1] = 'B'
list2 = [[0] * M for i in range(N)]
first = 0
distance = 0
whites = 0
js = 0
total = 0
for i in range(N):
	first = 0
	for j in range(M):
		if list1[i][j] == '.' and first == 0:
			whites = 0
			first = 1
			distance = 1
			for k in range(j + 1, M):
				if list1[i][k] == 'B':
					distance += 1
					if k != M - 1:
						first = 0
					break
				elif list1[i][k] == 'W':
					whites += 1
					distance += 1
					if whites > 1:
						if k != M - 1:
							first = 0
						whites = 0
						break
				elif list1[i][k] == '.':
					distance += 1
			js = j + 1
			js -= 1
			list2[i][j] = distance + 0
			total = total + distance
		elif list1[i][j] == '.':
			list2[i][j] = list2[i][js] - (j - js)
			total += list2[i][j]
		else:
			list2[i][j] = 0
	first = 0
print(total)


ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda : int(input())
ip = lambda : [int(w) for w in input().split()]
(n, m, w, b, *g) = ip()
dt = {i: [] for i in range(1, n + 1)}
for i in range(0, 2 * w, 2):
	dt[g[i]].append([g[i + 1], 'W'])
g = g[2 * w:]
for i in range(0, 2 * b, 2):
	dt[g[i]].append([g[i + 1], 'B'])
ans = 0
for i in range(1, n + 1):
	t = sorted(dt[i])
	if t == [] or t[-1][0] != m:
		t.append([m, 'B'])
		ans += 1
	else:
		t[-1][1] = 'B'
	prev = 1
	for j in range(len(t)):
		(ind, cell) = t[j]
		no = ind - prev
		if cell == 'B':
			l = 2
			r = ind - prev + 1
		else:
			nxt = t[j + 1][0]
			l = nxt - ind + 2
			r = nxt - prev + 1
		ans += no * (l + r) // 2
		prev = ind + 1
print(ans)


def suma(s, e, cnt):
	t = e - s
	if cnt < e:
		t_1 = e - cnt + 1
		ans = t * (t + 1) // 2 - t_1 * (t_1 + 1) // 2
	else:
		ans = t * (t + 1) // 2 - 1
	return ans
(n, m, w, b, *l) = list(map(int, input().split()))
dic = {}
for i in range(0, 2 * w, 2):
	(y, x) = (l[i] - 1, l[i + 1] - 1)
	if y not in dic:
		dic[y] = [[x, 1]]
	else:
		dic[y].append([x, 1])
for i in range(2 * w, 2 * (w + b), 2):
	(y, x) = (l[i] - 1, l[i + 1] - 1)
	if y not in dic:
		dic[y] = [[x, 2]]
	else:
		dic[y].append([x, 2])
ans = 0
for v in list(dic.values()):
	v.sort()
	v.append([m - 1, 2])
	i = len(v) - 1
	cnt_i = m + 1
	ans += 1
	while i >= 0:
		if i - 1 >= 0 and v[i - 1][1] == 2:
			ans += suma(v[i - 1][0], v[i][0], cnt_i)
			cnt_i = v[i - 1][0]
			i -= 1
		elif i - 2 >= 0 and v[i - 2][1] == 1:
			ans += suma(v[i - 2][0], v[i][0], cnt_i)
			if cnt_i != v[i - 1][0]:
				ans -= v[i][0] - v[i - 1][0] + 1
			cnt_i = v[i - 2][0]
			i -= 1
		elif i - 2 >= 0 and v[i - 2][1] == 2:
			ans += suma(v[i - 2][0], v[i][0], cnt_i)
			if cnt_i != v[i - 1][0]:
				ans -= v[i][0] - v[i - 1][0] + 1
			cnt_i = v[i - 2][0]
			i -= 2
		else:
			ans += suma(-1, v[i][0], cnt_i)
			if i == 1 and cnt_i != v[i - 1][0]:
				ans -= v[i][0] - v[i - 1][0] + 1
			break
n -= len(dic)
ans += n * m * (m + 1) // 2
print(ans)


(n, m, w, b, *l) = list(map(int, input().split()))
mat = [[0 for _ in range(m)] for _ in range(n)]
for i in range(w):
	(y, x) = (l[2 * i], l[2 * i + 1])
	mat[y - 1][x - 1] = 1
for i in range(w, w + b):
	(y, x) = (l[2 * i], l[2 * i + 1])
	mat[y - 1][x - 1] = 2
temp = [[0 for _ in range(m)] for _ in range(n)]
ans = 0
for j in range(n):
	prev_w = -1
	blk = m - 1
	for i in range(m - 1, -1, -1):
		if mat[j][i] == 2:
			blk = i
			prev_w = -1
		elif mat[j][i] == 1:
			if prev_w != -1:
				blk = prev_w
			prev_w = i
		else:
			ans += blk - i + 1
			temp[j][i] = blk - i + 1
print(ans)


it = list(map(int, input().split()))
(n, m) = it[:2]
(w, b) = it[2:4]
aa = it[4:4 + 2 * w]
aa = [[aa[i * 2], aa[i * 2 + 1]] for i in range(w)]
bb = it[4 + 2 * w:]
bb = [[bb[i * 2], bb[i * 2 + 1]] for i in range(b)]
ss = [[] for i in range(n)]
for i in aa:
	ss[i[0] - 1].append([i[1] - 1, 1])
for i in bb:
	ss[i[0] - 1].append([i[1] - 1, 0])
ss = [sorted(i) for i in ss]
tot = 0
for j in range(n):
	ind = 0
	co = 0
	st = []
	for i in ss[j]:
		if i[1] == 1:
			co += 1
			if co <= 1:
				st.append(i)
				continue
			a = i[0] - ind + 1
			b = 1 + 1
			for ii in st:
				a = ind
				b = ii[0] - 1
				a = i[0] - a + 1
				b = i[0] - b + 1
				su = (a + b) * (a - b + 1) // 2
				tot += su
				ind = ii[0] + 1
			st = [i[:]]
		else:
			co = 0
			a = i[0] - ind + 1
			b = 1 + 1
			su = (a + b) * (a - b + 1) // 2
			tot += su
			ind = i[0] + 1
			for ii in st:
				tot -= i[0] - ii[0] + 1
			st = []
	a = ind
	b = m - 1
	if a <= b:
		a = m - a
		b = m - b
		su = (a + b) * (a - b + 1) // 2
		tot += su
	for ii in st:
		tot -= m - ii[0]
print(tot)


arr = list(map(int, input().split()))
n = arr.pop(0)
m = arr.pop(0)
w = arr.pop(0)
b = arr.pop(0)
whites = {}
for i in range(0, 2 * w - 1, 2):
	x = arr[i] - 1
	y = arr[i + 1] - 1
	if x in whites:
		whites[x].append(y)
	else:
		whites[x] = [y]
blacks = {}
for i in range(2 * w, 2 * (w + b), 2):
	x = arr[i] - 1
	y = arr[i + 1] - 1
	if x in blacks:
		blacks[x].append(y)
	else:
		blacks[x] = [y]

def simulateRay(x, y):
	wRow = {}
	bRow = {}
	if x in whites:
		wRow = whites[x]
	if x in blacks:
		bRow = blacks[x]
	elif len(wRow) == 0 or (len(wRow) == 1 and wRow[0] != y):
		return m - y
	if y in wRow or y in bRow:
		return 0
	wCount = 0
	l = 1
	while y < m - 1:
		if y in wRow:
			wCount += 1
			if wCount == 2:
				return l
		if y in bRow:
			return l
		l += 1
		y += 1
	return l
total = 0
allL = int(m * (m + 1) / 2)
for i in range(n):
	if i in whites or i in blacks:
		for j in range(m):
			res = simulateRay(i, j)
			total += res
	else:
		total += allL
print(total)


x = list(map(int, input().strip().split()))
(n, m, w, b) = (x[0], x[1], x[2], x[3])
l = [[0] * m for _ in range(n)]
for i in range(4, 4 + 2 * w, 2):
	l[x[i] - 1][x[i + 1] - 1] = 1
for i in range(4 + 2 * w, 4 + 2 * w + 2 * b, 2):
	l[x[i] - 1][x[i + 1] - 1] = 2
ct = 0
del x
for x in l:
	(p1, p2, q) = (m, m, m)
	for i in range(m - 1, -1, -1):
		if x[i] == 2:
			q = i
		elif x[i] == 1:
			p2 = p1
			p1 = i
		else:
			ct += min(p2, q, m - 1) - i + 1
print(ct)


def solve(grid, row, col, white):
	s = 0
	for thing in grid[row]:
		for i in range(col, len(grid[row])):
			if grid[row][i] == 'B':
				s = i - col + 1
				return s
			elif grid[row][i] == 'W':
				white += 1
			if white == 2:
				s = i - col + 1
				return s
			if i + 1 == len(grid[row]):
				s = i - col + 1
				return s
	return s
arr = [int(x) for x in input().split()]
(n, m, w, b) = (arr[0], arr[1], arr[2], arr[3])
arr = arr[4:]
wh = []
bl = []
g = [['.' for i in range(m)] for j in range(n)]
for i in range(0, 2 * w - 1, 2):
	g[arr[i] - 1][arr[i + 1] - 1] = 'W'
for i in range(2 * w, len(arr) - 1, 2):
	g[arr[i] - 1][arr[i + 1] - 1] = 'B'
s = 0
for i in range(n):
	c = 0
	for j in range(m):
		if g[i][j] == 'W' or g[i][j] == 'B':
			c = 0
			continue
		if c == 0:
			c = solve(g, i, j, 0)
			s += c
		else:
			c -= 1
			s += c
print(s)


def solve(grid, row, col, white):
	s = 0
	for thing in grid[row]:
		for i in range(col, len(grid[row])):
			if grid[row][i] == 'B':
				s = i - col + 1
				return s
			elif grid[row][i] == 'W':
				white += 1
			if white == 2:
				s = i - col + 1
				return s
			if i + 1 == len(grid[row]):
				s = i - col + 1
				return s
	return s
array = [int(x) for x in input().split()]
(n, m, w, b) = (array[0], array[1], array[2], array[3])
array = array[4:]
white = []
black = []
grid = [['.' for i in range(m)] for j in range(n)]
for i in range(0, 2 * w - 1, 2):
	grid[array[i] - 1][array[i + 1] - 1] = 'W'
for i in range(2 * w, len(array) - 1, 2):
	grid[array[i] - 1][array[i + 1] - 1] = 'B'
s = 0
for i in range(n):
	current = 0
	for j in range(m):
		if grid[i][j] == 'W' or grid[i][j] == 'B':
			current = 0
			continue
		if current == 0:
			current = solve(grid, i, j, 0)
			s += current
		else:
			current -= 1
			s += current
print(s)