The city of Gridland is represented as an $n\times m$ matrix where the rows are numbered from $1$ to $n$ and the columns are numbered from $1$ to $m$.

Gridland has a network of train tracks that always run in straight horizontal lines along a row. In other words, the start and end points of a train track are $(r,c1)$ and $(r,c2)$, where $\textbf{r}$ represents the row number, $\mbox{c1}$ represents the starting column, and $c2$ represents the ending column of the train track. 

The mayor of Gridland is surveying the city to determine the number of locations where lampposts can be placed. A lamppost can be placed in any cell that is not occupied by a train track.

Given a map of Gridland and its $\boldsymbol{\mbox{k}}$ train tracks, find and print the number of cells where the mayor can place lampposts.

Note: A train track may overlap other train tracks within the same row. 

Example   

If Gridland's data is the following (1-based indexing):

k = 3
r   c1  c2
1   1   4
2   2   4
3   1   2
4   2   3

It yields the following map:

In this case, there are five open cells (red) where lampposts can be placed.

Function Description

Complete the gridlandMetro function in the editor below.  

gridlandMetro has the following parameter(s):  

int n:: the number of rows in Gridland
int m:: the number of columns in Gridland
int k:: the number of tracks
track[k][3]: each element contains $3$ integers that represent $\textbf{row},\textbf{column start},\textbf{column end}$, all 1-indexed   

Returns   

int: the number of cells where lampposts can be installed   

Input Format

The first line contains three space-separated integers $n,m$ and $\boldsymbol{\mbox{k}}$, the number of rows, columns and tracks to be mapped.   

Each of the next $\boldsymbol{\mbox{k}}$ lines contains three space-separated integers, $r,c1$ and $c2$, the row number and the track column start and end.  

Constraints

$1\leq n,m\leq10^9$
$0\leq k\leq1000$
$1\leq r\leq n$
$1\leq c1\leq c2\leq m$

Sample Input
STDIN   Function
-----   --------
4 4 3   n = 4, m = 4, k = 3
2 2 3   track = [[2, 2, 3], [3, 1, 4], [4, 4, 4]]
3 1 4
4 4 4

Sample Output
9

Explanation

In the diagram above, the yellow cells denote the first train track, green denotes the second, and blue denotes the third. Lampposts can be placed in any of the nine red cells.

Source: hackerrank | Difficulty: MEDIUM
Tags: Complete search


Solutions:
from collections import defaultdict
(n, m, k) = map(int, input().split())
tracks = defaultdict(list)
for _ in range(k):
	(row, c1, c2) = map(int, input().split())
	tracks[row].append((c1, -1))
	tracks[row].append((c2 + 1, 1))
ans = 0
for row in tracks:
	tracks[row].sort()
	prev = tracks[row][0][0]
	depth = 1
	for event in tracks[row][1:]:
		if depth > 0:
			ans += event[0] - prev
		depth -= event[1]
		prev = event[0]
print(n * m - ans)


(n, m, k) = map(int, input().split())
row_tracks = {}
for i in range(k):
	(r, c1, c2) = map(int, input().split())
	if r not in row_tracks:
		row_tracks[r] = []
	row_tracks[r].append((c1, c2))
total_occuppied = 0
for r in row_tracks:
	row_tracks[r].sort()
	current_occuppied = 0
	current_c2 = 0
	for track in row_tracks[r]:
		(c1, c2) = track
		if c1 <= current_c2:
			if c2 > current_c2:
				current_occuppied += c2 - current_c2
		else:
			current_occuppied += c2 - c1 + 1
		current_c2 = max(current_c2, c2)
	total_occuppied += current_occuppied
print(n * m - total_occuppied)


(n, m, k) = [int(x) for x in input().split()]
tracks = {}
taken = 0
for i in range(k):
	(r, c1, c2) = [int(x) for x in input().split()]
	l = c2 - c1 + 1
	row = tracks[r] if r in tracks else []
	for t in row:
		if c1 >= t[0] and c1 <= t[1]:
			c1 = t[1] + 1
		if c2 >= t[0] and c2 <= t[1]:
			c2 = t[0] - 1
		l = max(c2 - c1 + 1, 0)
		if l == 0:
			break
	if l > 0:
		row.append((c1, c2))
		tracks[r] = row
		taken += l
print(n * m - taken)


(N, M, K) = map(int, input().split())
D = {}
for k in range(K):
	(r, c1, c2) = map(int, input().split())
	if r not in D.keys():
		D[r] = []
	D[r] += [[c1, 1], [c2, -1]]
emptyFields = 0
for r in D.keys():
	X = {}
	for T in D[r]:
		if T[0] in X.keys():
			X[T[0]] += T[1]
		else:
			X[T[0]] = T[1]
	L = sorted(list(X.keys()))
	trains = 0
	for i in range(0, len(L)):
		if i == 0:
			emptyFields += L[0] - 1
		elif trains == 0:
			emptyFields += L[i] - L[i - 1] - 1
		trains += X[L[i]]
	emptyFields += M - L[-1]
emptyFields += (N - len(D.keys())) * M
print(emptyFields)


import sys
(n, m, k) = (int(x) for x in sys.stdin.readline().split())
tracks = {}
for _ in range(k):
	(r, c1, c2) = (int(x) for x in sys.stdin.readline().split())
	ts = tracks.get(r, [])
	if len(ts) == 0:
		ts.append((c1, c2))
	else:
		i = 0
		j = len(ts) - 1
		while j >= 0 and ts[j][1] >= c1:
			j -= 1
		while i < len(ts) and ts[i][0] <= c2:
			i += 1
		if j == len(ts) - 1:
			ts.append((c1, c2))
		elif i == 0:
			ts = [(c1, c2)] + ts
		else:
			c1 = min(c1, ts[j + 1][0])
			c2 = max(c2, ts[i - 1][1])
			ts = ts[:j + 1] + [(c1, c2)] + ts[i:]
	tracks[r] = ts
result = n * m
for r in tracks:
	for t in tracks[r]:
		result -= t[1] - t[0] + 1
print(result)


(n, m, k) = [int(v) for v in input().split(' ')]
train_tracks = []
for t in range(k):
	train_tracks.append([int(v) for v in input().split(' ')])
lamp = n * m
i = 0
train_tracks.sort()
while i < len(train_tracks) - 1:
	if train_tracks[i][0] == train_tracks[i + 1][0]:
		if train_tracks[i + 1][1] <= train_tracks[i][2]:
			train_tracks[i] = [train_tracks[i][0], min(train_tracks[i][1], train_tracks[i + 1][1]), max(train_tracks[i][2], train_tracks[i + 1][2])]
			train_tracks.pop(i + 1)
		else:
			i += 1
	else:
		i += 1
for t in train_tracks:
	lamp -= t[2] - t[1] + 1
print(lamp)


from collections import defaultdict
(n, m, k) = map(int, input().split())
counter = defaultdict(list)
for _ in range(k):
	(r, c, d) = map(int, input().split())
	counter[r].append([c, d])
res = n * m
for x in counter.values():
	x.sort()
	(pos, cur) = (0, 1)
	while cur != len(x):
		if x[cur][0] <= x[pos][1]:
			x[pos][1] = max(x[pos][1], x[cur][1])
			x.pop(cur)
		else:
			(pos, cur) = (cur, cur + 1)
	res -= sum(map(lambda i: i[1] - i[0] + 1, x))
print(res)


import sys
(row, col, k) = map(int, input().split())
dic = {}
if k == 0:
	print(row * col)
	sys.exit()
for i in range(k):
	(r, c1, c2) = map(int, input().split())
	if r not in dic:
		dic[r] = []
	_ = (c1, c2)
	dic[r].append(_)
total = row * col
for i in dic:
	size = len(dic[i])
	x = dic[i]
	x.sort()
	start = x[0][0]
	end = x[0][1]
	for j in range(1, size):
		if x[j][0] > end:
			total -= end - start + 1
			start = x[j][0]
			end = x[j][1]
		elif x[j][1] > end:
			end = x[j][1]
	total -= end - start + 1
print(total)


from collections import defaultdict

def r():
	return list(map(int, input().split()))

def ri():
	return int(input())

def main():
	(n, m, k) = r()
	tracks = defaultdict(list)
	occupied = 0
	for _ in range(k):
		(row, c1, c2) = r()
		tracks[row].append((c1, c2 + 1))
	for row in tracks:
		tracks[row].sort()
		cur_hi = -1
		for (lo, hi) in tracks[row]:
			lo = max(cur_hi, lo)
			occupied += max(0, hi - lo)
			cur_hi = max(hi, cur_hi)
	print(n * m - occupied)
main()


from collections import defaultdict
(N, M, K) = map(int, input().split())
rows = defaultdict(list)
for _ in range(K):
	(r, c1, c2) = map(int, input().split())
	rows[r].append((c1, c2))
ans = N * M
for k in rows.keys():
	rows[k].sort()
for row in rows.values():
	end = 0
	for (c1, c2) in row:
		if end < c1:
			ans -= c2 - c1 + 1
		elif c1 <= end < c2:
			ans -= c2 - end
		end = max(end, c2)
print(ans)


(d1, d2, k) = list(map(int, input().split()))
coords = [list(map(int, input().split())) for _ in range(k)]
coords = sorted(coords, key=lambda x: x[0])
m = {}
for c in coords:
	row = c[0]
	c1 = min(c[1], c[2])
	c2 = max(c[1], c[2])
	if row in m:
		m[row] = m[row] + [[c1, c2]]
	else:
		m[row] = [[c1, c2]]
m2 = []
for (k, v) in m.items():
	r = []
	for current in v:
		for stored in r:
			if not current or current[0] > current[1]:
				break
			if not stored or stored[0] > stored[1]:
				continue
			if current[0] >= stored[0] and current[1] <= stored[1]:
				current = None
				break
			if stored[0] >= current[0] and stored[1] <= current[1]:
				stored[1] = stored[0] - 1
				continue
			if current[0] < stored[0] and current[1] >= stored[0]:
				current[1] = stored[0] - 1
			if current[1] > stored[1] and current[0] <= stored[1]:
				current[0] = stored[1] + 1
		if current and current[0] <= current[1]:
			l = current[:]
			r.append(l)
			m2.append(l)
m2 = [x for x in m2 if x and x[1] >= x[0]]
occ = sum([x[1] - x[0] + 1 for x in m2])
total = d1 * d2 - occ
print(total)


def intersect(a, c):
	(a1, a2) = a
	(c1, c2) = c
	if max(a1, c1) <= min(a2, c2):
		return [[min(a1, c1), max(a2, c2)]]
	else:
		return [a, c]
(n, m, k) = [int(x) for x in input().split()]
rows = {}
res = n * m
for i in range(k):
	(r, c1, c2) = [int(x) for x in input().split()]
	if r in rows:
		rows[r].append([c1, c2])
	else:
		rows[r] = [[c1, c2]]
for r in rows:
	row = rows[r]
	sorted(row, key=lambda path: path[0])
	new_row = [row[0]]
	for i in range(1, len(row)):
		last_proc_path = new_row[-1]
		new_row = new_row[:-1]
		unproc_path = row[i]
		new_row += intersect(last_proc_path, unproc_path)
	for i in range(len(new_row)):
		res -= new_row[i][1] - new_row[i][0] + 1
print(res)


(m, n, k) = map(int, input().split())
res = 0
d = {}
for _ in range(k):
	(a, b, c) = map(int, input().split())
	if not a in d:
		d[a] = []
	d[a].append((b, 1))
	d[a].append((c, -1))
for (r, ts) in d.items():
	c = 0
	last = 0
	ts = sorted(ts)
	for i in range(len(ts)):
		t = ts[i]
		if c != 0:
			if c + t[1] == 0:
				res += t[0] - last + (1 if i == len(ts) - 1 or ts[i + 1][0] != t[0] else 0)
		if c == 0:
			last = t[0]
		c += t[1]
print(m * n - res)


(n, m, k) = [int(x) for x in input().strip().split(' ')]
tracks = {}
for _ in range(k):
	(r, c1, c2) = [int(x) for x in input().strip().split(' ')]
	tracks.setdefault(r, []).append((c1, c2))
lamps = n * m
for r in tracks:
	pairs = tracks[r]
	pairs.sort()
	merged = [pairs[0]]
	for (c1, c2) in pairs[1:]:
		if c1 > merged[0][1]:
			merged.insert(0, (c1, c2))
		else:
			new_c1 = merged[0][0]
			new_c2 = max(merged[0][1], c2)
			merged[0] = (new_c1, new_c2)
	taken = sum(map(lambda pair: pair[1] - pair[0] + 1, merged))
	lamps -= taken
print(lamps)


def mark_tracks(tracks, r, c1, c2):
	if r not in tracks:
		tracks[r] = []
	tracks[r].append((c1, c2))

def delete_overlapped_tracks(tracks):
	for r in tracks.keys():
		new_tracks_in_row = []
		tracks_in_row = sorted(tracks[r])
		(start, end) = tracks_in_row[0]
		for track in tracks_in_row:
			if track[0] >= start and track[0] <= end:
				end = max(end, track[1])
			else:
				new_tracks_in_row.append((start, end))
				(start, end) = track
		new_tracks_in_row.append((start, end))
		tracks[r] = new_tracks_in_row

def count_tracks(tracks):
	num = 0
	for (r, tracks_in_row) in tracks.items():
		for track in tracks_in_row:
			num += track[1] - track[0] + 1
	return num
(n, m, k) = input().strip().split(' ')
(n, m, k) = (int(n), int(m), int(k))
tracks = {}
for _ in range(k):
	(r, c1, c2) = input().strip().split(' ')
	(r, c1, c2) = (int(r), int(c1), int(c2))
	mark_tracks(tracks, r, c1, c2)
delete_overlapped_tracks(tracks)
print(n * m - count_tracks(tracks))


import math
(n, m, k) = list(map(int, input().split()))
tracks = {}
trackCount = {}
for i in range(k):
	(r, s, e) = list(map(int, input().split()))
	if s > e:
		(s, e) = (e, s)
	if r in tracks.keys():
		for (x, y) in tracks[r]:
			if x <= s and y >= e:
				(s, e) = (-1, -2)
			elif x <= s and y >= s:
				s = y + 1
			elif x <= e and y >= e:
				e = x - 1
		if e >= s:
			tracks[r].append((s, e))
			trackCount[r] += e - s + 1
	else:
		tracks[r] = [(s, e)]
		trackCount[r] = e - s + 1
ans = 0
for i in trackCount.keys():
	ans += trackCount[i]
print(n * m - ans)


(N, M, K) = map(int, input().split())
rail = {}
for _ in range(K):
	(r, f, t) = map(int, input().split())
	if r not in rail:
		rail[r] = []
	rail[r].append((t, f))
covered = 0
for x in rail:
	rail[x].sort()
	prv = (-1, -2)
	for p in rail[x]:
		p = (p[1], p[0])
		if p[0] <= prv[1]:
			tmp = min(prv[0], p[0])
			tmp2 = max(prv[1], p[1])
			prv = (tmp, tmp2)
		else:
			covered += prv[1] - prv[0] + 1
			prv = p
	covered += prv[1] - prv[0] + 1
ans = N * M - covered
print(ans)


import collections
(m, n, k) = [int(x) for x in input().split()]
cnt = m * n
d = collections.defaultdict(lambda : [])
for i in range(k):
	(r, c1, c2) = [int(x) for x in input().split()]
	if c2 < c1:
		(c1, c2) = (c2, c1)
	d[r].append((c1, c2))
for r in d:
	fin = []
	l = d[r]
	l.sort()
	tod = set()
	for i in range(len(l)):
		r1 = l[i][1]
		if i in tod:
			continue
		for k in range(i + 1, len(l)):
			if k in tod:
				continue
			if l[k][0] <= r1:
				r1 = max(l[k][1], r1)
				tod.add(k)
			else:
				break
		fin.append((l[i][0], r1))
	for (l1, r1) in fin:
		cnt -= r1 - l1 + 1
print(cnt)


(n, m, k) = [int(i) for i in input().split(' ')]
occ = 0
tracks = list()
for i in range(k):
	tracks.append([int(i) for i in input().split(' ')])
while len(tracks) > 0:
	tmp = list()
	tmp.append(tracks.pop(0))
	v = tmp[0][0]
	pos = 0
	while pos < len(tracks):
		if tracks[pos][0] == v:
			tmp.append(tracks.pop(pos))
		else:
			pos = pos + 1
	tmp.sort(key=lambda x: x[1])
	tm = tmp.pop(0)
	while len(tmp) > 0:
		te = tmp.pop(0)
		if te[1] <= tm[2]:
			tm[2] = max(te[2], tm[2])
		else:
			occ = occ + tm[2] - tm[1] + 1
			tm = te
	occ = occ + tm[2] - tm[1] + 1
print(n * m - occ)


import heapq

def get_points(s):
	i = 0
	while i < len(s) - 1:
		if s[i][0] <= s[i + 1][0] <= s[i][1]:
			new_point = (s[i][0], max(s[i][1], s[i + 1][1]))
			s[i:i + 2] = [new_point]
		else:
			i += 1
	num_points = 0
	for (a, b) in s:
		num_points += b - a + 1
	return num_points
(n, m, k, *_) = map(int, input().split())
S = {}
for _ in range(k):
	(r, c1, c2, *_) = map(int, input().split())
	heapq.heappush(S.setdefault(r, []), (c1, c2))
num_lampposts = m * n
for e in S.values():
	h = [heapq.heappop(e) for _ in range(len(e))]
	num_lampposts -= get_points(h)
print(num_lampposts)


def merge(intervals):
	sorted_by_lower_bound = sorted(intervals, key=lambda tup: tup[0])
	merged = []
	for higher in sorted_by_lower_bound:
		if not merged:
			merged.append(higher)
		else:
			lower = merged[-1]
			if higher[0] <= lower[1]:
				upper_bound = max(lower[1], higher[1])
				merged[-1] = (lower[0], upper_bound)
			else:
				merged.append(higher)
	return merged
(n, m, k) = map(int, input().split())
d = {}
for i in range(k):
	(r, c1, c2) = map(int, input().split())
	if r not in d:
		d[r] = []
	d[r].append((c1, c2))
for r in d:
	d[r] = merge(d[r])
ans = n * m
for i in d:
	for t in d[i]:
		ans -= t[1] - t[0] + 1
print(ans)


(n, m, k) = [int(x) for x in input().split(' ')]
from collections import defaultdict
grid = defaultdict(list)
for _ in range(k):
	(r, c1, c2) = [int(x) for x in input().split(' ')]
	g = grid[r]
	gx = []
	i = 0
	while i < len(g) and g[i + 1] < c1:
		gx.extend([g[i], g[i + 1]])
		i += 2
	if i == len(g):
		grid[r] = gx + [c1, c2]
		continue
	gx.append(min(g[i], c1))
	while i < len(g) and g[i + 1] < c2:
		i += 2
	if i == len(g):
		grid[r] = gx + [c2]
		continue
	if g[i] > c2:
		gx.append(c2)
	else:
		gx.append(g[i + 1])
		i += 2
	while i < len(g):
		gx.extend([g[i], g[i + 1]])
		i += 2
	grid[r] = gx
lamp = m * n
for r in grid:
	g = grid[r]
	for i in range(0, len(g), 2):
		lamp -= g[i + 1] + 1 - g[i]
print(lamp)


from collections import defaultdict
(n, m, k) = input().split(' ')
(n, m, k) = (int(n), int(m), int(k))

def merge_intervals(lista):
	n = len(lista)
	lista.sort(key=lambda element: (element[0], element[1]), reverse=True)
	index = 0
	for i in range(n):
		if index and lista[index - 1][0] <= lista[i][1]:
			while index and lista[index - 1][0] <= lista[i][1]:
				lista[index - 1][1] = max(lista[index - 1][1], lista[i][1])
				lista[index - 1][0] = min(lista[index - 1][0], lista[i][0])
				index -= 1
		else:
			lista[index] = lista[i]
		index += 1
	return lista[0:index]

def calcula_linha(lista):
	s = 0
	for l in lista:
		s += l[1] - l[0]
	return s
n_post = n * m
post_locations = defaultdict(list)
for i in range(k):
	(r, c1, c2) = input().split(' ')
	(r, c1, c2) = (int(r), int(c1), int(c2))
	post_locations[r].append([c1, c2 + 1])
	post_locations[r] = merge_intervals(post_locations[r])
counter = 0
for (key, value) in post_locations.items():
	counter += calcula_linha(value)
print(n_post - counter)


(N, M, K) = [int(i) for i in input().split()]
d = {}
for k in range(K):
	l = [int(i) for i in input().split()]
	if l[0] in d:
		d[l[0]] = sorted(d[l[0]] + [(l[1], l[2])], key=lambda k: k[1])
		d[l[0]] = sorted(d[l[0]] + [(l[1], l[2])], key=lambda k: k[0])
	else:
		d[l[0]] = [(l[1], l[2])]
cnt = N * M
for i in d:
	x = [k[0] for k in d[i]]
	y = [k[1] for k in d[i]]
	cnt -= y[0] - x[0] + 1
	for j in range(1, len(x)):
		if x[j] <= max(y[:j]):
			if y[j] > max(y[:j]):
				cnt -= y[j] - max(y[:j])
		elif x[j] > max(y[:j]):
			cnt -= y[j] - x[j] + 1
print(cnt)


def calcualate(array):
	i = 0
	count = 0
	result = [array[0]]
	for i in range(1, len(array)):
		start = result.pop(-1)
		if start[1] >= array[i][0]:
			result.append((start[0], max(start[1], array[i][1])))
		else:
			result.append(start)
			result.append(array[i])
	for each in result:
		count += each[1] - each[0] + 1
	return count
(n, m, k) = map(int, input().split())
count = 0
my_hash = {}
for i in range(k):
	(r, c1, c2) = map(int, input().split())
	if r not in my_hash:
		my_hash[r] = [(c1, c2)]
	else:
		my_hash[r].append((c1, c2))
for each in my_hash:
	my_hash[each].sort(key=lambda x: x[0])
	count += calcualate(my_hash[each])
print(n * m - count)


def range_overlap_adjust(list_ranges):
	overlap_corrected = []
	for (start, stop) in sorted(list_ranges):
		if overlap_corrected and start - 1 <= overlap_corrected[-1][1] and (stop >= overlap_corrected[-1][1]):
			overlap_corrected[-1] = (min(overlap_corrected[-1][0], start), stop)
		elif overlap_corrected and start <= overlap_corrected[-1][1] and (stop <= overlap_corrected[-1][1]):
			break
		else:
			overlap_corrected.append((start, stop))
	return overlap_corrected

def merge_trains3(arr):
	b = range_overlap_adjust(arr)
	summa = 0
	for i in b:
		summa += i[1] + 1 - i[0]
	return summa

def merge_trains(arr):
	s = set()
	for i in arr:
		s = s.union(set(range(i[0], i[1] + 1)))
	return len(s)

def merge_trains2(arr):
	b = []
	for (begin, end) in sorted(arr):
		if b and b[-1][1] >= begin - 1:
			b[-1][1] = max(b[-1][1], end)
		else:
			b.append([begin, end])
	summa = 0
	for i in b:
		summa += i[1] + 1 - i[0]
	return summa
(n, m, k) = [int(i) for i in input().strip().split()]
lamp_posts = n * m
train_dict = {}
for train in range(k):
	stri = [int(j) for j in input().strip().split()]
	row = stri[0]
	if row in train_dict.keys():
		train_dict[row].append(stri[1:])
	else:
		train_dict[row] = [stri[1:]]
for (key, value) in train_dict.items():
	lamp_posts -= merge_trains2(value)
print(lamp_posts)


import itertools
(n, m, k) = map(int, input().strip().split())
tracks = []
for i in range(0, k):
	(r, c1, c2) = map(int, input().strip().split())
	tracks.append([r, c1, c2])
tracks.sort()
for i in range(0, len(tracks)):
	j = i + 1
	while j < len(tracks):
		if tracks[i][0] == tracks[j][0] and tracks[i][2] >= tracks[j][1]:
			tracks[i][1] = min(tracks[i][1], tracks[j][1])
			tracks[i][2] = max(tracks[i][2], tracks[j][2])
			tracks.pop(j)
		else:
			j += 1
count = n * m - sum([track[2] - track[1] + 1 for track in tracks])
print(count)


def main():
	(nrows, ncols, ntracks) = readints()
	track = {}
	for _ in range(ntracks):
		(r, c1, c2) = readints()
		if r not in track:
			track[r] = ([c1], [c2])
		else:
			t = track[r]
			t[0].append(c1)
			t[1].append(c2)
	tcount = 0
	for t in track.values():
		tcount += counttrack(*t)
	print(nrows * ncols - tcount)

def readints():
	return [int(fld) for fld in input().strip().split()]

def counttrack(start, stop):
	start = sorted(start) + [1 + max(stop)]
	stop = sorted(stop)
	ans = trackness = istart = istop = 0
	while istop < len(stop):
		if start[istart] <= stop[istop]:
			if trackness == 0:
				starttrack = start[istart]
			trackness += 1
			istart += 1
		else:
			trackness -= 1
			if trackness == 0:
				ans += stop[istop] - starttrack + 1
			istop += 1
	return ans
main()


def getTrackLength(tracks):
	tracks = sorted(tracks)
	start = tracks[0][0]
	end = tracks[0][1]
	if len(tracks) == 1:
		return end - start + 1
	new_tracks = []
	for i in range(1, len(tracks)):
		s = tracks[i][0]
		e = tracks[i][1]
		if s <= end:
			if e > end:
				end = e
		else:
			new_tracks.append((start, end))
			start = s
			end = e
	new_tracks.append((start, end))
	count = 0
	for track in new_tracks:
		count += track[1] - track[0] + 1
	return count
(n, m, k) = map(int, input().strip().split())
row_track_dict = {}
for i in range(k):
	(row, start, end) = map(int, input().strip().split())
	if row not in row_track_dict.keys():
		row_track_dict[row] = [(start, end)]
	else:
		row_track_dict[row].append((start, end))
total_col_used = 0
for tracks in row_track_dict.values():
	total_col_used += getTrackLength(tracks)
print(n * m - total_col_used)


(m, n, t) = [int(x) for x in input().split()]
d = {}
for i in range(t):
	(r, c1, c2) = [int(x) for x in input().split()]
	if r in d:
		lower = 0
		upper = 0
		ll = False
		ul = False
		for j in range(len(d[r])):
			if c1 >= d[r][j][0] and c1 <= d[r][j][1] + 1:
				ll = True
				lower = j
				break
		for j in range(len(d[r])):
			if c2 >= d[r][j][0] - 1 and c2 <= d[r][j][1] + 1:
				ul = True
				upper = j
		if ll == True:
			if ul == True:
				d[r][lower:upper + 1] = [[min(d[r][lower][0], c1), max(d[r][upper][1], c2)]]
			else:
				d[r][lower:lower + 1] = [[min(d[r][lower][0], c1), c2]]
		elif ul == True:
			d[r][upper:upper + 1] = [[c1, max(d[r][upper][1], c2)]]
		else:
			wrap = False
			for k in range(len(d[r])):
				if d[r][k][0] > c1 and d[r][k][1] < c2:
					wrap = True
					d[r][k] = [c1, c2]
					break
			if not wrap:
				d[r].append([c1, c2])
		d[r].sort(key=lambda x: x[0])
	else:
		d[r] = [[c1, c2]]
t = m * n
for i in d:
	for j in d[i]:
		t -= j[1] - j[0] + 1
print(t)


(n, m, k) = [int(x) for x in input().split()]
track = {}
for i in range(k):
	(r, c1, c2) = [int(x) for x in input().split()]
	temp = track.get(r, [])
	if len(temp) == 0:
		temp.append((c1, c2))
		track[r] = temp
	else:
		j = 0
		f = True
		while j < len(temp):
			t = temp[j]
			if c2 < t[0] - 1:
				temp.insert(j, (c1, c2))
				break
			elif c2 >= t[0] - 1 and c2 <= t[1]:
				if c1 >= t[0]:
					break
				temp[j] = (c1, t[1])
				break
			elif c1 >= t[0] and c1 <= t[1] + 1:
				if c2 <= t[1]:
					break
				c1 = t[0]
				temp.pop(j)
			else:
				j += 1
		if j >= len(temp):
			temp.insert(j, (c1, c2))
ce = 0
for k in track:
	row = track.get(k)
	for x in row:
		ce += x[1] - x[0] + 1
print(n * m - ce)


import sys
(n, m, k) = input().strip().split()
(n, m, k) = (int(n), int(m), int(k))
trains = {}
for i in range(k):
	(r, c1, c2) = input().strip().split()
	(r, c1, c2) = (int(r), min(int(c1), int(c2)), max(int(c1), int(c2)))
	newRow = [[c1, c2]]
	if r in trains:
		for t in trains[r]:
			if c1 <= t[1] and t[0] <= c2:
				newRow[0] = [min(c1, t[0]), max(c2, t[1])]
			else:
				newRow.append(t)
	trains[r] = newRow
total = n * m
for row in trains:
	for t in trains[row]:
		total -= t[1] - t[0] + 1
print(total)


(n, m, k) = map(int, input().strip().split())
rows = {}
for _ in range(k):
	(r, c0, c1) = map(int, input().strip().split())
	todelete = []
	if r in rows:
		row = rows[r]
		for t in row:
			if c1 >= t[0] and c0 <= t[1]:
				todelete.append(t)
				c0 = min(c0, t[0])
				c1 = max(c1, t[1])
		for t in todelete:
			row.remove(t)
		row.append((c0, c1))
	else:
		rows[r] = [(c0, c1)]
total = n * m
for r in rows:
	for t in rows[r]:
		total -= t[1] - t[0] + 1
print(total)


(n, m, k) = tuple(map(int, input().split()))
dic = {}
for i in range(k):
	(r, c1, c2) = tuple(map(int, input().split()))
	if r not in dic:
		dic[r] = {}
	if c1 not in dic[r]:
		dic[r][c1] = 0
	if c2 + 1 not in dic[r]:
		dic[r][c2 + 1] = 0
	dic[r][c1] = dic[r][c1] + 1
	dic[r][c2 + 1] = dic[r][c2 + 1] - 1
res = 0
for r in dic:
	tracks = dic[r]
	keys = tracks.keys()
	keys = sorted(keys)
	st = 0
	now = 0
	for col in keys:
		if now > 0:
			res = res + col - st
		now = now + tracks[col]
		st = col
print(n * m - res)


def rem(r):
	lenr = len(r)
	if lenr == 1:
		t = r[0]
		return t[1] - t[0] + 1
	x = 0
	r.sort()
	(m, lenm) = ([], 0)
	m0 = -1
	for t in r:
		if t[0] == m0:
			if m[lenm - 1][1] < t[1]:
				m[lenm - 1][1] = t[1]
		else:
			m.append(t)
			lenm += 1
			m0 = t[0]
	for i in range(0, lenm - 1):
		if m[i][1] >= m[i + 1][0]:
			m[i + 1][0] = m[i][0]
			m[i + 1][1] = max(m[i][1], m[i + 1][1])
			m[i][0] = -1
	for i in range(0, lenm):
		if m[i][0] != -1:
			x += m[i][1] - m[i][0] + 1
	return x
(n, m, k) = map(int, input().strip().split(' '))
T = []
for i in range(0, k):
	(r, c1, c2) = map(int, input().strip().split(' '))
	T.append([r, c1, c2])
lent = len(T)
ans = n * m
if lent == 0:
	print(ans)
elif lent == 1:
	ans -= T[0][2] - T[0][2] + 1
	print(ans)
else:
	T.sort()
	R = []
	i = 0
	while True:
		row = [T[i][1:]]
		if i == lent - 1:
			R.append(row)
			break
		while T[i][0] == T[i + 1][0]:
			row.append(T[i + 1][1:])
			i += 1
			if i == lent - 1:
				break
		R.append(row)
		i += 1
		if i == lent:
			break
	for row in R:
		y = rem(row)
		ans -= y
	print(ans)


def get_intervals(intervals):
	sorted_by_lower_bound = sorted(intervals, key=lambda tup: tup[0])
	merged = []
	for higher in sorted_by_lower_bound:
		if not merged:
			merged.append(higher)
		else:
			lower = merged[-1]
			if higher[0] <= lower[1]:
				upper_bound = max(lower[1], higher[1])
				merged[-1] = (lower[0], upper_bound)
			else:
				merged.append(higher)
	return merged

def test():
	(n, m, k) = map(int, input().split())
	lines = {}
	for _ in range(k):
		(r, c1, c2) = map(int, input().split())
		if r not in lines:
			lines[r] = []
		lines[r].append([c1, c2])
	tot = 0
	for x in lines:
		intervals = get_intervals(lines[x])
		subtot = m
		for x in intervals:
			subtot -= x[1] - x[0] + 1
		tot += subtot
	tot += (n - len(lines)) * m
	print(tot)
test()


(n, m, k) = (int(x) for x in input().split())

def intersect(ab, xy):
	if ab[0] <= xy[0] and ab[1] >= xy[0]:
		return True
	if ab[0] <= xy[1] and ab[1] >= xy[1]:
		return True
	return False

def superinterval(ab, xy):
	return (min(ab[0], xy[0]), max(ab[1], xy[1]))
tracks = dict()
for i in range(k):
	(r, c1, c2) = (int(x) for x in input().split())
	t = (c1, c2)
	deletion = []
	if r not in tracks:
		tracks[r] = [t]
		continue
	for (i, interval) in enumerate(tracks[r]):
		if intersect(interval, t):
			t = superinterval(interval, t)
			deletion.append(i)
	for i in reversed(deletion):
		del tracks[r][i]
	tracks[r].append(t)
covered = 0
for row in tracks:
	for track in tracks[row]:
		covered += track[1] - track[0] + 1
print(n * m - covered)


(n, m, k) = [int(x) for x in input().strip().split()]
trains = {}
for i in range(k):
	(r, c1, c2) = [int(x) for x in input().strip().split()]
	if r - 1 not in trains:
		trains[r - 1] = []
	trains[r - 1].append((c1 - 1, c2 - 1))

def combine_row(row):
	cur = row[0]
	result = []
	for (c1, c2) in row[1:]:
		if cur[0] <= c1 <= cur[1]:
			cur = (cur[0], max(cur[1], c2))
		else:
			result.append(cur)
			cur = (c1, c2)
	result.append(cur)
	return result
lamps = 0
for r in trains:
	ls = 0
	for (c1, c2) in combine_row(sorted(trains[r])):
		ls += c2 - c1 + 1
	lamps += m - ls
lamps += (n - len(trains)) * m
print(lamps)


(n, m, k) = list(map(int, input().split(' ')))
total = m * n
rect = {}
for _q in range(k):
	(r, c1, c2) = list(map(int, input().split(' ')))
	if r in rect:
		rect[r].append((c1, c2))
	else:
		rect[r] = [(c1, c2)]
subt = 0
for (_key, liste) in rect.items():
	sorted_list = sorted(liste)
	last_tup_end = 0
	for tup in sorted_list:
		start = tup[0]
		end = tup[1]
		if start <= last_tup_end:
			start = last_tup_end + 1
		subt += max(0, end - start + 1)
		last_tup_end = max(last_tup_end, end)
print(total - subt)


(n, m, k) = list(map(int, input().split()))
count = n * m
d = dict()
for _ in range(k):
	(r, c1, c2) = list(map(int, input().split()))
	if not r in d:
		d[r] = []
	toRemove = []
	for i in range(len(d[r])):
		item = d[r][i]
		if item[0] < c1:
			if item[1] < c1:
				continue
			c1 = item[0]
			if item[1] > c2:
				c2 = item[1]
			toRemove.append(i)
		elif item[0] == c1:
			if item[1] > c2:
				c2 = item[1]
			toRemove.append(i)
		else:
			if item[1] > c2:
				continue
			toRemove.append(i)
			if item[0] < c1:
				c1 = item[0]
	for i in toRemove[::-1]:
		del d[r][i]
	d[r].append((c1, c2))
for item in d.values():
	for j in item:
		count -= j[1] - j[0] + 1
print(count)


(n, m, k) = [int(item) for item in input().strip().split()]
c = 0
overlap = [0] * k
rs = []
op = 0
for i in range(k):
	(r, s, e) = [int(item) for item in input().strip().split()]
	c += e - s + 1
	if r not in rs:
		rs.append(r)
		overlap[rs.index(r)] = [s, e]
	else:
		if e in range(overlap[rs.index(r)][0], overlap[rs.index(r)][1] + 1):
			op += e - max(overlap[rs.index(r)][0], s) + 1
		elif s in range(overlap[rs.index(r)][0], overlap[rs.index(r)][1] + 1):
			op += min(overlap[rs.index(r)][1], e) - s + 1
		(overlap[rs.index(r)][0], overlap[rs.index(r)][1]) = (min(overlap[rs.index(r)][0], s), max(overlap[rs.index(r)][1], e))
print(n * m - c + op)


s = 0
(n, m, k) = [int(x) for x in input().split()]
d = {}
for i in range(k):
	(r, c1, c2) = [int(x) for x in input().split()]
	if r not in d:
		d[r] = list()
	d[r].append((c1, c2))
for (k, v) in d.items():
	s1 = 0
	v = sorted(v)
	mn = 0
	mx = 0
	for (c1, c2) in v:
		if mn == 0 and mx == 0:
			s1 += c2 - c1 + 1
			mn = c1
			mx = c2
		elif c1 >= mn and c1 <= mx and (c2 >= mx):
			s1 += c2 - mx
			mx = c2
		elif c1 > mx:
			s1 += c2 - c1 + 1
			mn = c1
			mx = c2
	s += s1
print(n * m - s)


(n, m, k) = map(int, input().split())
x = dict()
val = n * m
for i in range(k):
	(r, c1, c2) = map(int, input().split())
	if r not in x:
		x[r] = (c1, c2)
	else:
		if x[r][1] < c1:
			val += c1 - x[r][1] - 1
		elif x[r][0] > c2:
			val += x[r][0] - c2 - 1
		x[r] = (min(x[r][0], c1), max(x[r][1], c2))
for t in x.values():
	val -= t[1] - t[0] + 1
print(val)


(rows, columns, tracks) = map(int, input().split())
grid = {}
for i in range(tracks):
	aux = tuple(map(int, input().split()))
	if aux[0] in grid:
		grid[aux[0]].append((aux[1], aux[2]))
	else:
		grid[aux[0]] = [(aux[1], aux[2])]
lamppost = (rows - len(grid)) * columns
for r in grid:
	auxR = grid[r]
	auxR = sorted(auxR)
	changes = True
	while changes:
		changes = False
		for i in range(1, len(auxR)):
			if auxR[i][0] <= auxR[i - 1][1]:
				changes = True
				auxR = [(auxR[i - 1][0], max(auxR[i - 1][1], auxR[i][1]))] + auxR[i + 1:]
				break
	sumTracks = 0
	for tr in auxR:
		sumTracks += tr[1] - tr[0] + 1
	lamppost += columns - sumTracks
print(lamppost)


import sys
x = sys.stdin.readlines()
(N, M, K) = [int(i) for i in x[0].split(' ')]
S = 0
d = {}
for i in range(1, K + 1):
	(r, c1, c2) = [int(j) for j in x[i].split(' ')]
	if r not in d:
		d[r] = []
	d[r].append((c1, c2))

def qsort(L):
	if L:
		return qsort([x for x in L if x < L[0]]) + [x for x in L if x == L[0]] + qsort([x for x in L if x > L[0]])
	return []

def lamps_in_row(r):
	A = []
	B = []
	for i in r:
		(a, b) = i
		A.append(a)
		B.append(b)
	A = qsort(A)
	B = qsort(B)
	C = qsort(A + B)
	a_i = 0
	b_i = 0
	s = 0
	for i in range(len(C)):
		count = a_i - b_i
		if i > 0 and count == 0:
			s = C[i] - C[i - 1] - 1
		if a_i < len(A) and C[i] == A[a_i]:
			a_i = a_i + 1
		elif b_i < len(B) and C[i] == B[b_i]:
			b_i = b_i + 1
	return (s, A[0], B[-1])
for i in d:
	(s, a, b) = lamps_in_row(d[i])
	S = S + (b - a + 1 - s)
print(M * N - S)


prams = list(map(int, input().split()))
dic = {}
s = 0
for a in range(prams[2]):
	[r, c1, c2] = list(map(int, input().split()))
	if r not in dic:
		dic[r] = [(c1, c2)]
		s += c2 - c1 + 1
	else:
		i = 0
		for [k1, k2] in dic[r]:
			if c1 <= k1 and c2 >= k1 or (c2 >= k2 and c1 <= k2) or (c1 >= k1 and c2 <= k2):
				dic[r].pop(i)
				s -= k2 - k1 + 1
				c1 = min(c1, k1)
				c2 = max(c2, k2)
				s += c2 - c1 + 1
				dic[r].append((c1, c2))
				break
			i += 1
		else:
			s += c2 - c1 + 1
			dic[r].append((c1, c2))
s = prams[0] * prams[1] - s
s = max(s, 0)
print(s)


[m, n, numTracks] = [int(i) for i in input().strip().split(' ')]
rows = {}

class Point:

	def __init__(self, tup):
		self.tup = tup

	def __eq__(self, other):
		if isinstance(other, A):
			return self.tup == other.tup
		return NotImplemented

	def __ne__(self, other):
		result = self.__eq__(other)
		if result is NotImplemented:
			return result
		return not result

	def __lt__(self, other):
		return self.tup[1] - other.tup[1] < 0 or (self.tup[1] == other.tup[1] and self.tup[0] == 1)

	def __gt__(self, other):
		return self.tup[1] - other.tup[1] > 0 or (self.tup[1] == other.tup[1] and self.tup[0] == 2)

	def __le__(self, other):
		return self.__eq__(other) or self.__lt__(other)

	def __ge__(self, other):
		return self.__eq__(other) or self.__gt__(other)

	def __getitem__(self, index):
		return self.tup[index]

	def __repr__(self):
		return str(self.tup)

	def __str__(self):
		return str(self.tup)
for i in range(numTracks):
	tokens = input().strip().split(' ')
	l = [Point((1, int(tokens[1]))), Point((2, int(tokens[2])))]
	if rows.get(tokens[0], None) is None:
		rows[tokens[0]] = l
	else:
		rows[tokens[0]] += l
covered = 0
for i in rows:
	rows[i].sort()
	s = 0
	start = 0
	e = 0
	for tup in rows[i]:
		if tup[0] is 1:
			if s is 0:
				start = tup[1]
			s += 1
		else:
			e += 1
		if s is e:
			covered += tup[1] - start + 1
			s = 0
			e = 0
			start = 0
print(m * n - covered)


import sys
import bisect
from collections import namedtuple

class TrackTuple(namedtuple('_TrackTuple', ['c1', 'c2'])):

	def __lt__(self, o):
		return self.c1 < o.c1

	def __len__(self):
		return self.c2 - self.c1 + 1

	def combine(self, o):
		c1 = self.c1 if self.c1 <= o.c1 else o.c1
		c2 = self.c2 if self.c2 >= o.c2 else o.c2
		return TrackTuple(c1, c2)
(rows, cols, k) = [int(i) for i in input().strip().split(' ')]
n_tracks = 0
rails = {}
for j in range(k):
	(r, c1, c2) = [int(i) for i in input().strip().split(' ')]
	if c1 > c2:
		(c1, c2) = (c2, c1)
	track = TrackTuple(c1, c2)
	row_track = rails.setdefault(r, [])
	row_track_len = len(row_track)
	if row_track_len == 0:
		row_track.append(track)
		track_len = len(track)
	else:
		i = bisect.bisect(row_track, track)
		rm_list = []
		if i > 0:
			t = row_track[i - 1]
			if c1 <= t.c2:
				track = track.combine(t)
				rm_list.append(t)
		if i < row_track_len:
			t = row_track[i + 1]
			if c2 >= t.c1:
				track_len -= t.c2 - c1 + 1
				track = track.combine(t)
				rm_list.append(t)
		old_len = sum((len(t) for t in row_track))
		row_track.insert(i, track)
		for t in rm_list:
			row_track.remove(t)
		new_len = sum((len(t) for t in row_track))
		track_len = new_len - old_len
	n_tracks += track_len
print(rows * cols - n_tracks)


import sys
(n, m, k) = input().strip().split(' ')
n = int(n)
m = int(m)
traindict = {}
count = n * m
for i in range(int(k)):
	(row, c1, c2) = input().strip().split(' ')
	row = int(row)
	c1 = int(c1)
	c2 = int(c2)
	if row in traindict:
		if c1 < traindict[row][0]:
			if c2 < traindict[row][0]:
				count = count - (c2 - c1 + 1)
				traindict[row][0] = c1
			else:
				count = count - (traindict[row][0] - c1)
				traindict[row][0] = c1
		if c2 > traindict[row][1]:
			if c1 > traindict[row][1]:
				count = count - (c2 - c1 + 1)
				traindict[row][1] = c2
			else:
				count = count - (c2 - traindict[row][1])
				traindict[row][1] = c2
	else:
		traindict[row] = [c1, c2]
		count = count - (c2 - c1 + 1)
print(count)


from collections import defaultdict
(n, m, k) = [int(i) for i in input().strip().split(' ')]
d = defaultdict(lambda : list())
for test in range(k):
	(r, c1, c2) = [int(i) for i in input().strip().split(' ')]
	d[r].append([c1, c2])
total = 0
for (keys, values) in d.items():
	v = sorted(values, key=lambda x: x[0])
	start = v[0][0]
	end = v[0][1]
	for i in range(1, len(v)):
		data = v[i]
		if data[0] <= end:
			end = max(end, data[1])
		else:
			total += end - start + 1
			start = data[0]
			end = data[1]
	total += end - start + 1
print(n * m - total)


(N, M, k) = [int(n) for n in input().split()]
total = 0
trains = []
for _ in range(k):
	trains.append([int(n) for n in input().split()])
trains.sort(key=lambda x: x[0])
total = 0
prevRow = 1
occ = 0
prevEnd = 0
for train in trains:
	if train[0] > prevRow:
		total += (train[0] - prevRow) * M - occ
		occ = 0
		prevEnd = 0
		prevRow = train[0]
	if train[2] > prevEnd:
		if train[1] > prevEnd:
			occ += train[2] - train[1] + 1
		else:
			occ += train[2] - prevEnd
		prevEnd = max(prevEnd, train[2])
total += (N + 1 - prevRow) * M - occ
print(total)


from collections import defaultdict
(n, m, k) = map(int, input().split())
l = []
for _ in range(k):
	l.append([int(x) for x in input().strip().split()])
d = defaultdict(list)
for x in l:
	d[x[0]].append((x[1], x[2]))
new_l = []
for x in d.keys():
	new_l.append(sorted(d[x], key=lambda x: (x[0], x[1])))
tot = 0
for x in new_l:
	(temp1, temp2) = x[0]
	for (c1, c2) in x:
		if c1 in range(temp1, temp2 + 1) and c2 in range(temp1, temp2 + 1):
			continue
		if c1 in range(temp1, temp2 + 1):
			(temp1, temp2) = (temp1, c2)
		else:
			tot += temp2 - temp1 + 1
			(temp1, temp2) = (c1, c2)
	tot += temp2 - temp1 + 1
print(n * m - tot)


line1 = input().strip().split(' ')
n = int(line1[0])
m = int(line1[1])
k = int(line1[2])
trackDict = {}
for x in range(k):
	track = list(map(int, input().strip().split(' ')))
	endPoints = track[1:]
	if track[0] in trackDict:
		rowList = trackDict[track[0]]
		i = 0
		while i < len(rowList) and rowList[i][0] < endPoints[0]:
			i = i + 1
		rowList.insert(i, endPoints)
	else:
		trackDict[track[0]] = [track[1:]]
totalOccupiedSquares = 0
for row in trackDict:
	rowList = trackDict[row]
	aIndex = 0
	bIndex = 1
	while bIndex < len(rowList):
		a = rowList[aIndex]
		b = rowList[bIndex]
		if b[0] <= a[1]:
			rowList[aIndex] = [a[0], max(a[1], b[1])]
			del rowList[bIndex]
		else:
			aIndex += 1
			bIndex += 1
	for item in rowList:
		totalOccupiedSquares += item[1] - item[0] + 1
print(m * n - totalOccupiedSquares)


import sys
from collections import defaultdict, deque
from itertools import islice, chain
ROW = 0
C1 = 1
C2 = 2

def main(text=None):
	(n, m, trains) = parse_input(text)
	num_cells = n * m
	if len(trains) == 0:
		return num_cells
	trains = merge_trains(trains)
	occupied = count_occupied(trains)
	return num_cells - occupied

def parse_input(text=None):
	if not text:
		text = sys.stdin.read().rstrip()
	lines = [list(map(int, l.rstrip().split(' '))) for l in text.split('\n')]
	(n, m, k) = lines[0]
	trains = lines[1:]
	return (n, m, trains)

def merge_trains(all_trains):
	trains_by_row = defaultdict(list)
	for train in all_trains:
		row = train[ROW]
		trains_by_row[row].append(train)
	new_trains_by_row = defaultdict(list)
	for (row, trains) in trains_by_row.items():
		if len(trains) == 1:
			new_trains_by_row[row].append(trains[0])
			continue
		trains = sorted(trains, key=lambda x: x[1:])
		last_two = deque(trains[0:1], maxlen=2)
		for t in islice(trains, 1, None):
			last_two.append(t)
			if last_two[0][C2] + 1 >= last_two[1][C1]:
				merged_train = [row, last_two[0][C1], max(last_two[0][C2], last_two[1][C2])]
				last_two[1] = merged_train
			else:
				new_trains_by_row[row].append(last_two[0])
		new_trains_by_row[row].append(last_two[1])
	return list(chain.from_iterable(new_trains_by_row.values()))

def count_occupied(trains):
	return sum((t[C2] - t[C1] + 1 for t in trains))
print(main())


import itertools
from collections import deque

def calculate_lenghts(intervals):
	current_interval = intervals.popleft()
	combined_length = 0
	while intervals:
		next_interval = intervals.popleft()
		if current_interval[1] + 1 < next_interval[0]:
			combined_length += current_interval[1] - current_interval[0] + 1
			current_interval = next_interval
		else:
			current_interval = (current_interval[0], max(current_interval[1], next_interval[1]))
	combined_length += current_interval[1] - current_interval[0] + 1
	return combined_length
(row_count, col_count, n) = [int(x) for x in input().split()]
grid = []
for _ in range(n):
	grid.append([int(x) for x in input().split()])
grid.sort()
grid_by_row = {}
for (k, g) in itertools.groupby(grid, lambda x: x[0]):
	grid_by_row[k] = deque()
	for (r, c1, c2) in g:
		grid_by_row[k].append((c1, c2))
result = 0
for row in grid_by_row:
	lengths = calculate_lenghts(grid_by_row[row])
	result += col_count - lengths
result += col_count * (row_count - len(grid_by_row))
print(result)


(rows, cols, numTracks) = [int(x) for x in input().strip().split()]
tracks = dict()
for _ in range(numTracks):
	(r, c1, c2) = [int(x) for x in input().strip().split()]
	if r not in tracks:
		tracks[r] = [[c1, c2]]
	else:
		found = False
		foundTrack = None
		for track in tracks[r]:
			if c1 >= track[0] and c2 <= track[1]:
				found = True
				foundTrack = track
				break
			elif c1 <= track[0] and c2 >= track[1]:
				track[0] = c1
				track[1] = c2
				found = True
				foundTrack = track
				break
			elif c1 < track[0] and track[0] <= c2 <= track[1]:
				track[0] = c1
				found = True
				foundTrack = track
				break
			elif c2 > track[1] and track[0] <= c1 <= track[1]:
				track[1] = c2
				found = True
				foundTrack = track
				break
		if not found:
			tracks[r].append([c1, c2])
		else:
			for track in tracks[r].copy():
				if track == foundTrack:
					continue
				elif track[0] <= foundTrack[1]:
					track[0] = foundTrack[1] + 1
				elif track[1] >= foundTrack[0]:
					track[1] = foundTrack[0] - 1
				if track[1] < track[0]:
					tracks[r].remove(track)
trackSquares = 0
for v in tracks.values():
	for track in v:
		trackSquares += track[1] - track[0] + 1
print(rows * cols - trackSquares)


def main():
	(n, m, k) = [int(temp) for temp in input().strip().split(' ')]
	t = n * m
	x = {}
	c = 0
	for i in range(k):
		(r, c1, c2) = [int(temp) for temp in input().strip().split(' ')]
		if r in x.keys():
			(xc1, xc2) = (x[r][0], x[r][1])
			if not (c2 < xc1 or c1 > xc2):
				if c1 <= xc1 and c2 >= xc2:
					c -= xc2 - xc1 + 1
					x[r] = [c1, c2]
				elif c1 > xc1 and c2 >= xc2:
					c -= xc2 - c1 + 1
					x[r][1] = c2
				elif c1 <= xc1 and c2 < xc2:
					c -= c2 - xc1 + 1
					x[r][0] = c1
				else:
					continue
		else:
			x[r] = [c1, c2]
		c += c2 - c1 + 1
	print(t - c)
main()


(m, n, k) = map(int, input().split())
lamp = 0
b = {}
for i in range(k):
	(r, c1, c2) = map(int, input().split())
	if r not in b:
		b[r] = [[c1, c2]]
	else:
		b[r].append([c1, c2])
for i in b.keys():
	b[i].sort(key=lambda l: l[0])
	flag = 1
	while flag:
		flag = 0
		for j in range(len(b[i]) - 1):
			if b[i][j][1] >= b[i][j + 1][0]:
				flag = 1
				if b[i][j][1] < b[i][j + 1][1]:
					b[i][j][1] = b[i][j + 1][1]
				b[i].pop(j + 1)
				break
for i in b.keys():
	temp = 0
	for j in range(len(b[i])):
		temp += b[i][j][1] - b[i][j][0] + 1
	lamp += n - temp
lamp += (m - len(b.keys())) * n
print(lamp)


(N, M, K) = tuple(map(int, input().split()))
r_situation = {}
for _ in range(K):
	(r, begin, end) = tuple(map(int, input().split()))
	if not r_situation.get(r):
		r_situation[r] = []
	r_situation[r].append((begin, end))
track_spaces = 0
for R in r_situation.values():
	R.sort()
	track_spaces += R[0][1] - R[0][0] + 1
	for idx in range(1, len(R)):
		track_pair = R[idx]
		longest_track_end = -1
		for log_idx in range(idx - 1, -1, -1):
			log_track_pair = R[log_idx]
			if track_pair[0] <= log_track_pair[1]:
				longest_track_end = max(longest_track_end, log_track_pair[1])
		if longest_track_end == -1:
			track_spaces += track_pair[1] - track_pair[0] + 1
		elif longest_track_end <= track_pair[1]:
			track_spaces += track_pair[1] - longest_track_end
print(N * M - track_spaces)


def Overlap_interval(inp):
	res = []
	if len(inp) == 1:
		return inp
	length = len(inp)
	i = 0
	j = 0
	while i < length:
		start = inp[i][0]
		end = inp[i][1]
		while j < length and (start <= inp[j][0] and inp[j][1] <= end or (start <= inp[j][0] and inp[j][0] <= end)):
			end = max(end, inp[j][1])
			j += 1
		i = j
		j += 1
		res.append((start, end))
	return res
(n, m, k) = map(int, input().strip().split())
name_map = {}
num = 0
inp = []
for i in range(k):
	(r, c1, c2) = map(int, input().strip().split())
	if r in name_map.keys():
		index = name_map[r]
		inp[index].append((c1, c2))
	else:
		name_map[r] = num
		index = num
		inp.append([])
		inp[-1].append((c1, c2))
		num += 1
result = n * m
for i in range(len(inp)):
	inp[i].sort()
	inp[i] = Overlap_interval(inp[i])
	for j in inp[i]:
		value = j[1] - j[0] + 1
		result -= value
print(result)


def mergeTwoTracks(t1, t2):
	start = 0
	end = 0
	if t1[1] <= t2[1]:
		start = t1[1]
	else:
		start = t2[1]
	if t1[2] >= t2[2]:
		end = t1[2]
	else:
		end = t2[2]
	return [t1[0], start, end]

def checkIntersection(t1, t2):
	if t1[0] != t2[0]:
		return False
	if t1[1] >= t2[1] and t1[1] <= t2[2]:
		return True
	if t1[2] <= t2[2] and t1[2] >= t2[1]:
		return True
	if t2[1] >= t1[1] and t2[1] <= t1[2]:
		return True
	if t2[2] <= t1[2] and t2[2] >= t1[1]:
		return True
	return False

def checkForMerge(tracks):
	for i in range(len(tracks) - 1):
		curr = tracks[i]
		for j in range(i + 1, len(tracks)):
			if checkIntersection(curr, tracks[j]):
				tracks[i] = mergeTwoTracks(curr, tracks[j])
				tracks.remove(tracks[j])
				return [tracks, True]
	return [tracks, False]
line = list(map(int, input().split(' ')))
tracks = []
for i in range(line[2]):
	tracks.append(list(map(int, input().split(' '))))
check = True
while check:
	result = checkForMerge(tracks)
	tracks = result[0]
	check = result[1]
taken = 0
for i in range(len(tracks)):
	taken += tracks[i][2] - tracks[i][1] + 1
taken = line[0] * line[1] - taken
print(taken)


def within(num, tup):
	return num >= tup[0] and num <= tup[1]
(n, m, k) = (int(i) for i in input().split())
tracks = {}
num = 0
for _ in range(k):
	(r, c1, c2) = (int(i) - 1 for i in input().split())
	if r not in tracks:
		tracks[r] = []
	tracks[r].append((c1, c2))
for r in tracks:
	if len(tracks[r]) == 1:
		num += tracks[r][0][1] - tracks[r][0][0] + 1
	else:
		final = []
		row = sorted(tracks[r], key=lambda x: x[0])
		for i in range(len(row) - 1):
			if within(row[i + 1][0], row[i]):
				if within(row[i + 1][1], row[i]):
					final.append(row[i])
				else:
					final.append((row[i][0], row[i + 1][1]))
				row[i + 1] = final[-1]
			else:
				final.append(row[i])
		repeats = [track[0] for track in row]
		for (i, elem) in enumerate(repeats):
			if elem in repeats[i + 1:]:
				row[i] = False
		for track in row:
			if track:
				num += track[1] - track[0] + 1
print(n * m - num)


def row_calc(array):
	n = len(array)
	array = sorted(array)
	new_array = []
	answer = 0
	prev_1 = array[0][1]
	prev_2 = array[0][2]
	for x in range(n - 1):
		if prev_2 >= array[x + 1][1]:
			if prev_2 >= array[x + 1][2]:
				array[x + 1][1] = prev_2
				array[x + 1][2] = prev_2 - 1
			else:
				array[x + 1][1] = prev_2 + 1
				prev_1 = array[x + 1][1]
				prev_2 = array[x + 1][2]
		else:
			prev_1 = array[x + 1][1]
			prev_2 = array[x + 1][2]
	for x in range(n):
		answer += array[x][2] - array[x][1] + 1
	return answer
(n, m, k) = list((int(x) for x in input().split()))
tracks = []
for x in range(k):
	track = list((int(x) for x in input().split()))
	tracks.append(track)
tracks = sorted(tracks)
answer1 = 0
x = 0
while x < k:
	track_list = []
	track_list.append(tracks[x])
	try:
		while tracks[x][0] == tracks[x + 1][0]:
			track_list.append(tracks[x + 1])
			x += 1
	except:
		pass
	answer1 += row_calc(track_list)
	x += 1
answer = n * m - answer1
print(answer)


(row_count, column_count, track_count) = map(int, input().strip().split(' '))
row_usage = dict()
for track in range(track_count):
	(row, start_column, stop_column) = map(int, input().strip().split(' '))
	row_sections = row_usage.get(row)
	if row_sections is None:
		row_usage[row] = [[start_column, stop_column]]
	else:
		new_used = []
		for section in row_sections:
			if section[1] < start_column or stop_column < section[0]:
				new_used.append(section)
			else:
				start_column = min(start_column, section[0])
				stop_column = max(stop_column, section[1])
		new_used.append((start_column, stop_column))
		row_usage[row] = new_used
free_cells_count = row_count * column_count
for (row_number, row_sections) in row_usage.items():
	for section in row_sections:
		free_cells_count -= section[1] - section[0] + 1
print(free_cells_count)


from operator import itemgetter

def fun(temp, m):
	n = len(temp)
	temp.sort(key=itemgetter(0))
	ans = [[temp[0][0], temp[0][1]]]
	for i in range(1, n):
		if temp[i][0] <= ans[-1][1]:
			if temp[i][1] > ans[-1][1]:
				ans[-1] = [ans[-1][0], temp[i][1]]
		else:
			ans.append([temp[i][0], temp[i][1]])
	res = 0
	for i in ans:
		res += i[1] - i[0] + 1
	return m - res
(n, m, k) = [int(i) for i in input().split()]
a = [[0, 0, 0] for i in range(k)]
for i in range(k):
	a[i] = [int(j) for j in input().split()]
a.sort(key=itemgetter(0))
ans = 0
ind = 0
(start, end) = (0, 0)
c = 0
while ind < k:
	temp = []
	start = a[ind][1]
	end = a[ind][2]
	temp.append([start, end])
	ind += 1
	c += 1
	while ind < k and a[ind][0] == a[ind - 1][0]:
		start = a[ind][1]
		end = a[ind][2]
		ind += 1
		temp.append([start, end])
	ans += fun(temp, m)
ans += (n - c) * m
print(ans)


(n, m, k) = [int(i) for i in input().split()]
ans = 0
d = {}
for _ in range(k):
	(r, c1, c2) = [int(i) for i in input().split()]
	if r not in d:
		d[r] = [c1, c2]
	elif d[r][0] <= c1 <= d[r][1] or d[r][0] <= c2 <= d[r][1]:
		t1 = min(c1, d[r][0])
		t2 = max(c2, d[r][1])
		d[r] = [t1, t2]
	else:
		if c1 > d[r][1]:
			ans -= c1 - d[r][1] - 1
		else:
			ans -= d[r][0] - c2 - 1
		t1 = min(c1, d[r][0])
		t2 = max(c2, d[r][1])
		d[r] = [t1, t2]
for i in d:
	ans += d[i][1] - d[i][0] + 1
print(n * m - ans)


def main():
	(rowNum, colNum, trackNum) = map(int, input().strip().split(' '))
	intervalListDict = dict()
	for trackIdx in range(trackNum):
		(r, c1, c2) = map(int, input().strip().split(' '))
		intervalListDict[r] = intervalListDict.get(r, [])
		intervalListDict[r].append((c1, c2))
	coveredCells = 0
	for intervalList in intervalListDict.values():
		coveredCells += countCoveredCells(intervalList)
	print(rowNum * colNum - coveredCells)

def countCoveredCells(intervalList):
	merged = []
	for i in sorted(intervalList, key=lambda i: i[0]):
		if merged and i[0] <= merged[-1][1]:
			merged[-1] = (merged[-1][0], max(merged[-1][1], i[1]))
		else:
			merged.append(i)
	cells = 0
	for i in merged:
		cells += i[1] - i[0] + 1
	return cells
main()


import sys
from collections import defaultdict
lines = sys.stdin.read().rstrip().split('\n')

def createTrainInfoDict(trainInfo):
	row_to_trains = defaultdict(list)
	for train in trainInfo:
		(row, start, end) = [int(i) for i in train.split()]
		row_to_trains[row].append((start, end))
	return row_to_trains

def countNonAvailableSpotsInRow(trains, r_num):
	trains = sorted(trains, key=lambda train: train[0])
	numUnavailableSpots = 0
	currentEndPoint = 0
	for train in trains:
		if train[1] > currentEndPoint:
			offset = 0
			if train[0] <= currentEndPoint:
				offset = currentEndPoint - train[0] + 1
			length = train[1] - train[0] + 1
			numUnavailableSpots += length - offset
			currentEndPoint = train[1]
	return numUnavailableSpots

def countNumberOfSpots(lines):
	(r_num, c_num, k_num) = [int(i) for i in lines[0].split()]
	if k_num == 0:
		return r_num * c_num
	rows_to_trains = createTrainInfoDict(lines[1:])
	available = r_num * c_num
	for row_key in rows_to_trains:
		available -= countNonAvailableSpotsInRow(rows_to_trains[row_key], r_num)
	return available
print(countNumberOfSpots(lines))


(n, m, k) = [int(x) for x in input().split()]
train = []
for i in range(0, k):
	(r, c1, c2) = [int(x) for x in input().split()]
	train.append((r, c1, c2))
train.sort()
(row, startT, endT) = (0, 0, 0)
(total, rowtrain) = (0, 0)
rch = False
for item in train:
	if item[0] != row:
		rch = True
		total = total + (rowtrain + (endT - startT + 1))
		(row, startT, endT) = item
		rowtrain = 0
	else:
		rch = False
		if item[1] <= endT:
			if endT < item[2]:
				endT = item[2]
		else:
			rowtrain = rowtrain + (endT - startT + 1)
			startT = item[1]
			endT = item[2]
if rch:
	total += endT - startT + 1
else:
	total += rowtrain + (endT - startT + 1)
total = total - 1
print(m * n - total)


(n, m, k) = map(int, input().split())
total = n * m
d = {}
t = 0
for _ in range(k):
	(r, c1, c2) = map(int, input().split())
	if r not in d:
		d[r] = []
		d[r].append(c1)
		d[r].append(c2)
	else:
		if c2 < d[r][0]:
			t += d[r][0] - c2 - 1
		if c1 > d[r][1]:
			t += c1 - d[r][1] - 1
		if c1 <= d[r][0] and c2 >= d[r][1]:
			t = 0
		if c1 < d[r][0]:
			d[r][0] = c1
		if c2 > d[r][1]:
			d[r][1] = c2
for k in d:
	total = total - (d[k][1] - d[k][0] + 1) + t
print(total)


class Track:

	def __init__(self, c1, c2):
		self.c1 = c1
		self.c2 = c2

	def __lt__(self, d):
		if self.c1 == d.c1:
			return self.c2 < d.c2
		return self.c1 < d.c1
(n, m, k) = [int(x) for x in input().split()]
rows = {}
for _ in range(k):
	(r, c1, c2) = [int(x) for x in input().split()]
	if r not in rows:
		rows[r] = []
	rows[r].append(Track(c1, c2))
result = n * m
for (r, row) in rows.items():
	row.sort()
	r_n = len(row)
	total = 0
	(st, ed) = (row[0].c1, row[0].c2)
	for i in range(1, r_n):
		track = row[i]
		if track.c1 <= ed:
			ed = max(ed, track.c2)
		else:
			total -= ed - st + 1
			(st, ed) = (track.c1, track.c2)
	total -= ed - st + 1
	result += total
print(result)


import copy

def sortIt(x):
	i = 0
	while i < len(x) - 2:
		j = i + 2
		min = i
		while j < len(x):
			if x[min] > x[j]:
				min = j
			j += 2
		if min != i:
			(x[i], x[i + 1], x[min], x[min + 1]) = (x[min], x[min + 1], x[i], x[i + 1])
		i += 2
(n, m, k) = (int(x) for x in input().split())
tracks = {}
while k > 0:
	(r, c1, c2) = (int(x) for x in input().split())
	if r not in tracks.keys():
		tracks[r] = [c1, c2]
	else:
		tracks[r].append(c1)
		tracks[r].append(c2)
	k -= 1
count = 0
for row in tracks.keys():
	temp = copy.deepcopy(tracks[row])
	sortIt(temp)
	count += temp[1] - temp[0] + 1
	start = 2
	daddy = temp[1]
	while start < len(temp):
		if temp[start] > daddy:
			count += temp[start + 1] - temp[start] + 1
			daddy = temp[start + 1]
		elif temp[start] <= daddy:
			if temp[start + 1] >= daddy:
				count += temp[start + 1] - daddy
				daddy = temp[start + 1]
		start += 2
print(n * m - count)


from collections import defaultdict

def merge_ranges(ranges):
	ranges = iter(sorted(ranges))
	(current_start, current_stop) = next(ranges)
	for (start, stop) in ranges:
		if start > current_stop:
			yield (current_start, current_stop)
			(current_start, current_stop) = (start, stop)
		else:
			current_stop = max(current_stop, stop)
	yield (current_start, current_stop)

def main():
	d = defaultdict(list)
	(n, m, k) = map(int, input().split())
	res = 0
	for _ in range(k):
		line = [int(a) for a in input().split(' ')]
		d[line[0]].append(line[1:])
	for ranges in d.values():
		l = list(merge_ranges(ranges))
		res += sum((l[i][0] - l[i - 1][1] - 1 for i in range(1, len(l))))
		res += l[0][0] - 1 + (m - l[-1][1])
	res += (n - len(d)) * m
	print(res)
main()


import sys
from collections import defaultdict

def count_cells(rset):
	ranges = sorted(map(list, rset))
	merged = [ranges[0]]
	for r in ranges[1:]:
		if r[0] <= merged[-1][1]:
			merged[-1][1] = max(merged[-1][1], r[1])
		else:
			merged.append(r)
	return sum((x[1] - x[0] + 1 for x in merged))
it = map(int, sys.stdin.read().split())
(n, m) = (next(it), next(it))
next(it)
tracks = defaultdict(set)
for (r, c1, c2) in zip(it, it, it):
	tracks[r].add((c1, c2))
cells_in_rows = (count_cells(ranges) for ranges in tracks.values())
print(m * n - sum(cells_in_rows))


(n, m, k) = input().split(' ')
(n, m, k) = [int(n), int(m), int(k)]
tracks = []
for t1 in range(k):
	tracks.append([int(t) for t in input().split(' ')])
tracks.sort()
if k == 0:
	print(n * m)
else:
	r = tracks[0][0]
	c1 = tracks[0][1]
	c2 = tracks[0][2]
	count = (r - 1) * m
	prev_row = r
	non_over_laps = 0
	for i in range(1, k):
		if tracks[i][0] == prev_row:
			c3 = tracks[i][1]
			c4 = tracks[i][2]
			if c3 <= c2 and c4 > c2:
				c2 = c4
			elif c3 > c2:
				non_over_laps += c2 - c1 + 1
				c1 = c3
				c2 = c4
		else:
			count += (tracks[i][0] - prev_row - 1) * m
			if non_over_laps > 0:
				count += m - (c2 - c1 + 1) - non_over_laps
			else:
				count += m - (c2 - c1 + 1)
			prev_row = tracks[i][0]
			c1 = tracks[i][1]
			c2 = tracks[i][2]
			non_over_laps = 0
	if non_over_laps > 0:
		count += m - (c2 - c1 + 1) - non_over_laps
	else:
		count += m - (c2 - c1 + 1)
	if prev_row < n:
		count += (n - prev_row) * m
	print(count)


import sys
from operator import itemgetter, attrgetter, methodcaller

def create_grid(nr, mc):
	return [[1 for i in range(nr)] for j in range(mc)]

def mark_track(grid, r, c1, c2):
	r0 = r - 1
	for c in range(c1 - 1, c2):
		grid[c][r0] = 0

def count_free(grid):
	res = 0
	for col in grid:
		res += sum(col)
	return res

class Track(object):
	r = None
	c1 = None
	c2 = None

	def __init__(self, r_, c1_, c2_):
		self.r = r_
		self.c1 = min(c1_, c2_)
		self.c2 = max(c1_, c2_)

	def getLength(self):
		return self.c2 - self.c1 + 1

	def _sortKey(self):
		return (self.r, self.c1, 1.0 / self.getLength())

	def __cmp__(self, other):
		return self._sortKey().__cmp__(other._sortKey())

	def __cmp__(self, other):
		return self._sortKey().__cmp__(other._sortKey())

	def getR(self):
		return self.r

	def getC1(self):
		return self.c1

	def getC2(self):
		return self.c2

	def doesOverlap(self, other):
		if self._sortKey() <= other._sortKey():
			(t1, t2) = (self, other)
		else:
			(t1, t2) = (other, self)
		return (t1.getR() == t2.getR()) & (t1.getC2() >= t2.getC1())

	def createContaining(self, other):
		return Track(self.r, min(self.getC1(), other.getC1()), max(self.getC2(), other.getC2()))

def sumUsed(tracks):
	sum = 0
	for track in tracks:
		sum += track.getLength()
	return sum

def do_it():
	(n, m, k) = [int(c_temp) for c_temp in input().strip().split(' ')]
	tracks = []
	for trackIdx in range(k):
		(r, c1, c2) = [int(c_temp) for c_temp in input().strip().split(' ')]
		tracks.append(Track(r, c1, c2))
	tracks = sorted(tracks, key=methodcaller('_sortKey'))
	if len(tracks) > 0:
		tlast = tracks[0]
		tail = tracks[1:]
		tracks = []
		for tnext in tail:
			if tlast.doesOverlap(tnext):
				tlast = tlast.createContaining(tnext)
			else:
				tracks.append(tlast)
				tlast = tnext
		tracks.append(tlast)
	print('%d' % (n * m - sumUsed(tracks)))
do_it()


from collections import defaultdict

def count_elements(ranges):
	ranges.sort()
	result_ranges = []
	while ranges:
		first = ranges.pop(0)
		while ranges:
			n = ranges[0]
			if first[0] <= n[0] <= first[1] or first[0] <= n[1] <= first[1]:
				first = (min(first[0], n[0]), max(first[1], n[1]))
				ranges.pop(0)
			else:
				break
		result_ranges.append(first)
	return sum((e - s + 1 for (s, e) in result_ranges))
d = defaultdict(list)
(n, m, k) = map(int, input().split())
for _ in range(k):
	(r, s, e) = map(int, input().split())
	d[r].append((s, e))
d = {r: count_elements(ranges) for (r, ranges) in d.items()}
print(n * m - sum(d.values()))


(a, b, c) = input().strip().split(' ')
(a, b, c) = [int(a), int(b), int(c)]
d = {}
w = {}
for i in range(c):
	(r, c1, c2) = input().strip().split(' ')
	(r, c1, c2) = [int(r), int(c1), int(c2)]
	if r in d:
		f = d[r]
		if c2 < f[0] - 1:
			w[r] = f[0] - 1 - c2
		if c1 > f[1] + 1:
			w[r] = c1 - f[1] - 1
		f[0] = min(f[0], c1)
		f[1] = max(f[1], c2)
		d[r] = f
	else:
		d[r] = [c1, c2]
		w[r] = 0
m = 0
for k in d:
	m += d[k][1] - d[k][0] + 1 - w[k]
x = a * b - m
print(x)


(n, m, k) = [int(x) for x in input().split()]
total = n * m
tracks = {}
for _ in range(k):
	(r, start, end) = [int(x) for x in input().split()]
	tracks.setdefault(r, []).append((start, end))
occupied = 0
for (key, values) in tracks.items():
	values.sort(key=lambda x: x[0])
	last = -1
	for (start, end) in values:
		if start <= last:
			start = last + 1
		sl = end - start + 1
		if sl > 0:
			occupied += sl
			last = end
print(total - occupied)


def count_lamposts(n, m, tracks):
	tracks.sort()
	count = 0
	(r, c1, c2) = (0, 0, 0)
	for (ri, ci, cj) in tracks:
		if ri != r:
			count += m - c2 if r > 0 else 0
			count += (ri - (r + 1)) * m
			(r, c1, c2) = (ri, 0, 0)
		if ci > c2:
			count += ci - (c2 + 1)
			c1 = ci
		if cj > c2:
			c2 = cj
	count += m - c2 if r > 0 else 0
	count += (n - r) * m
	return count
(n, m, k) = [int(n) for n in input().split()]
tracks = [[int(n) for n in input().split()] for _ in range(k)]
print(count_lamposts(n, m, tracks))


(m, n, k) = [int(i) for i in input().strip().split(' ')]
tracks = {}
for _ in range(k):
	(r, c1, c2) = [int(i) for i in input().strip().split(' ')]
	if r not in tracks.keys():
		tracks[r] = [[c1, c2]]
	else:
		for j in tracks[r]:
			merged = False
			if c1 >= j[0] and c1 <= j[1]:
				j[1] = max(j[1], c2)
				merged = True
			if c2 >= j[0] and c2 <= j[1]:
				j[0] = min(j[0], c1)
				merged = True
			if not merged:
				tracks[r].append([c1, c2])
			break
res = n * m
for i in tracks.keys():
	for j in tracks[i]:
		res -= j[1] - j[0] + 1
print(res)


import sys
(n, m, k) = [int(i) for i in input().split()]
rows = {}
non = 0
for i in range(k):
	(row_k, c1, c2) = input().split()
	c1 = int(c1)
	c2 = int(c2)
	if row_k in rows.keys():
		if c1 - rows[row_k][1] > 1:
			non += c1 - rows[row_k][1] - 1
		rows[row_k][0] = min(c1, rows[row_k][0])
		rows[row_k][1] = max(c2, rows[row_k][1])
	else:
		rows[row_k] = [c1, c2]
total_cells = n * m
occupied_cells = sum([1 + i[1] - i[0] for i in rows.values()])
print(total_cells - occupied_cells + non)


(n, m, k) = map(int, input().split())
trains = {}
for i in range(k):
	(r, left, right) = map(int, input().split())
	if r in trains:
		trains[r].append((left, right))
	else:
		trains[r] = [(left, right)]

def merge(tracks, i):
	if i >= len(tracks):
		return (-1, 0, 0)
	else:
		left = tracks[i][0]
		right = tracks[i][1]
		for j in range(i + 1, len(tracks)):
			if tracks[j][0] > right:
				return (j, left, right)
			else:
				right = max(right, tracks[j][1])
		return (k, left, right)
occupiedCells = 0
for r in trains:
	tracks = trains[r]
	tracks.sort(key=lambda x: x[0])
	i = 0
	while i < k:
		result = merge(tracks, i)
		i = result[0]
		if i != -1:
			occupiedCells += result[2] - result[1] + 1
print(n * m - occupiedCells)


(n, m, k) = input().strip().split(' ')
(n, m, k) = (int(n), int(m), int(k))

def insert(l, a, b):
	start = -1
	end = len(l)
	for i in range(len(l)):
		if a > l[i]:
			start = i
		if b < l[i]:
			end = i
			break
	return l[:start + 1] + [a] * (start % 2) + [b] * ((end + 1) % 2) + l[end:]
dct = {}
for train_track in range(k):
	(r, c1, c2) = input().strip().split(' ')
	(r, c1, c2) = (int(r), int(c1), int(c2))
	dct[r] = insert(dct.get(r, []), c1, c2)
total = n * m
for v in dct.values():
	for j in range(0, len(v), 2):
		total -= v[j + 1] - v[j] + 1
print(total)


from operator import itemgetter
(n, m, k) = map(int, input().split(' '))
g_ = [tuple(map(int, input().split(' '))) for i in range(k)]
g = sorted(g_, key=itemgetter(0, 1, 2))
tracks = {}

def squidge(row):
	flag = False
	for (i, cur) in enumerate(row):
		if i == 0:
			continue
		(c1, c2) = cur
		(xc1, xc2) = row[i - 1]
		if c2 <= xc2:
			del row[i]
			flag = True
			break
		if c1 <= xc2:
			row[i - 1][1] = c2
			del row[i]
			flag = True
			break
	if flag:
		squidge(row)
for (r, c1, c2) in g:
	if r not in tracks:
		tracks[r] = [[c1, c2]]
	else:
		tracks[r].append([c1, c2])
for r in tracks:
	squidge(tracks[r])
taken = 0
for r in tracks:
	for t in tracks[r]:
		taken += t[1] - t[0] + 1
print(n * m - taken)


class track:

	def __init__(self):
		self.start = -1
		self.stop = -1
		self.next = None

def printInsert(before, after):
	print('Insert between <', end='')
	if before == None:
		print('None', end='')
	else:
		print(before.start, ':', before.stop, end='')
	print('> and <', end='')
	if after == None:
		print('None', end='')
	else:
		print(after.start, ':', after.stop, end='')
	print('>')

def insertTrack(t, a, b):
	before = None
	after = t
	head = t
	addNew = True
	while True:
		if after == None:
			break
		if before == None and b <= after.stop:
			break
		if a < after.start:
			break
		before = after
		after = after.next
	if after != None and a >= after.start and (b <= after.stop):
		return head
	if before != None and a <= before.stop + 1:
		addNew = False
		before.stop = b
	if addNew:
		newT = track()
		newT.start = a
		newT.stop = b
		newT.next = after
		if before == None:
			head = newT
		else:
			before.next = newT
		before = newT
	while after != None and b >= after.start - 1:
		before.next = after.next
		if b > after.stop:
			before.stop = b
		else:
			before.stop = after.stop
		after = before.next
	return head

def printTracks(t):
	print('--- BEGIN ---')
	while t != None:
		print(t.start, ':', t.stop)
		t = t.next
	print('--- END ---')
	print()

def testInput():
	t = None
	while True:
		inpSplit = input().split()
		a = int(inpSplit[0])
		b = int(inpSplit[1])
		t = insertTrack(t, a, b)
		printTracks(t)
inpSplit = input().split()
rowCount = int(inpSplit[0])
colCount = int(inpSplit[1])
trackCount = int(inpSplit[2])
tracks = {}
for i in range(0, trackCount):
	inpSplit = input().split()
	row = int(inpSplit[0])
	colStart = int(inpSplit[1])
	colEnd = int(inpSplit[2])
	if row not in tracks:
		tracks[row] = None
	tracks[row] = insertTrack(tracks[row], colStart, colEnd)
sum = 0
dictionaryRowCount = 0
for key in tracks:
	t = tracks[key]
	rowSum = colCount
	while t != None:
		rowSum -= t.stop - t.start + 1
		t = t.next
	sum += rowSum
	dictionaryRowCount += 1
sum += (rowCount - dictionaryRowCount) * colCount
print(sum)


def checkTrackRange(oldVals, start, end):
	newRange = list()
	if oldVals[0] <= start and start <= oldVals[1] or (start <= oldVals[0] and oldVals[0] <= end):
		s = min(oldVals[0], start)
	if oldVals[0] <= end and end <= oldVals[1] or (start <= oldVals[1] and oldVals[1] <= end):
		e = max(oldVals[1], end)
	if oldVals[1] < start or start < oldVals[0]:
		return None
	newRange.append(s)
	newRange.append(e)
	return newRange

def getRangesum(hashMap):
	sum = 0
	for (k, v) in hashMap.items():
		i = 0
		while i <= len(v) - 2:
			sum += abs(v[i] - v[i + 1]) + 1
			i += 2
	return sum

def generateRestCellCount(tracks):
	hashMap = dict()
	for line in tracks:
		vals = line.split(' ')
		if len(vals) == 3:
			k = int(vals[0])
			if k in hashMap:
				oldVals = hashMap[k]
				if oldVals is not None:
					newRange = checkTrackRange(oldVals, int(vals[1]), int(vals[2]))
					if newRange is None:
						oldVals.append(int(vals[1]))
						oldVals.append(int(vals[2]))
						hashMap[k] = oldVals
					else:
						hashMap[k] = newRange
			else:
				newRange = [int(vals[1]), int(vals[2])]
				hashMap[k] = newRange
	sum = getRangesum(hashMap)
	return sum
(n, m, k) = input().strip().split(' ')
tracks = list()
for i in range(int(k)):
	track = input().strip()
	tracks.append(track)
sum = generateRestCellCount(tracks)
restCellCount = int(n) * int(m) - sum
if restCellCount > 0:
	print(restCellCount)
else:
	print(0)


(n, m, k) = map(int, input().split())
rows = {}
for i in range(k):
	(x, y1, y2) = map(int, input().split())
	if x in rows:
		rows[x].append([y1, y2])
	else:
		rows[x] = [[y1, y2]]
for row in rows:
	joined = []
	curr = sorted(rows[row], key=lambda x: (x[0], m - x[1]))[0]
	for i in range(1, len(rows[row])):
		if rows[row][i][0] <= curr[1]:
			curr[1] = max(rows[row][i][1], curr[1])
		else:
			joined.append(curr)
			curr = rows[row][i]
	joined.append(curr)
	rows[row] = joined
ans = (n - len(rows)) * m
for row in rows:
	k = 0
	for segment in rows[row]:
		k += segment[1] - segment[0] + 1
	ans += m - k
print(ans)


from collections import defaultdict
from operator import itemgetter
(n, m, k) = map(int, input().split())
tracks = []
if k == 0:
	print(n * m)
elif k == 1:
	(row, start, end) = map(int, input().split())
	print(n * m - (end - start))
else:
	for __ in range(k):
		(row, start, end) = map(int, input().split())
		tracks.append([row, (start, end)])
	tracks = sorted(tracks, key=itemgetter(0))
	merged_tracks = defaultdict(list)
	for track in tracks:
		merged_tracks[track[0]] += [track[1]]
	rows = sorted(merged_tracks)
	row_expected = 1
	free_space = n * m
	for row in rows:
		crazy_tracks = sorted(merged_tracks[row])
		valid_tracks = []
		for crazy_track in crazy_tracks:
			start = crazy_track[0]
			end = crazy_track[1]
			if not valid_tracks:
				valid_tracks.append((start, end))
				continue
			replaced = False
			for index in range(len(valid_tracks)):
				v_track = valid_tracks[index]
				v_start = v_track[0]
				v_end = v_track[1]
				if start <= v_start:
					if end <= v_end and end > v_end:
						valid_tracks[index] = (start, v_end)
						replaced = True
					elif end >= v_end:
						valid_tracks[index] = (start, end)
						replaced = True
				elif start > v_start and start <= v_end:
					if end <= v_end:
						replaced = True
						continue
					elif end >= v_end:
						valid_tracks[index] = (v_start, end)
						replaced = True
			if not replaced:
				valid_tracks.append((start, end))
		space_taken = 0
		for track in valid_tracks:
			space_taken += track[1] - track[0] + 1
		free_space -= space_taken
	print(free_space)


(n, m, k) = map(int, input().split())
rs = {}
for _ in range(k):
	(r, cs, ce) = map(int, input().split())
	rs.setdefault(r, []).append((cs, ce))
result = (n - len(rs)) * m
for trains in rs.values():
	trains.sort()
	last = 0
	for (start, end) in trains:
		if start > last + 1:
			result += start - last - 1
		last = max(last, end)
	result += m - last
print(result)


(n, m, k) = map(int, input().split())
tracks = [list(map(int, input().split())) for _ in range(k)]
tracks.sort()
i = 1
active = 0
disabled = [False] * k
while i < len(tracks):
	if tracks[active][0] == tracks[i][0] and tracks[i][1] <= tracks[active][2]:
		disabled[i] = True
		tracks[active][2] = max(tracks[i][2], tracks[active][2])
	else:
		active = i
	i += 1
print(n * m - sum((tracks[i][2] - tracks[i][1] + 1 for i in range(k) if not disabled[i])))


import sys
from operator import itemgetter

def counter(lst):
	lst.sort(key=itemgetter(0))
	i = 0
	while i < len(lst) - 1:
		first = lst[i]
		second = lst[i + 1]
		if second[0] <= first[1]:
			lst.remove(first)
			lst.remove(second)
			lst.insert(i, [first[0], max(first[1], second[1])])
		else:
			i += 1
	count = 0
	for item in lst:
		count += item[1] - item[0] + 1
	return count
tri = list(map(int, input().strip().split(' ')))
(n, m, k) = (tri[0], tri[1], tri[2])
dct = {}
rowlist = []
rowcount = 0
for _ in range(k):
	tri = list(map(int, input().strip().split(' ')))
	row = tri[0]
	c1 = tri[1]
	c2 = tri[2]
	if dct.get(row) == None:
		dct[row] = [[c1, c2]]
		rowlist.append(row)
		rowcount += 1
	else:
		dct[row].append([c1, c2])
count = (n - rowcount) * m
for item in rowlist:
	count += m - counter(dct[item])
print(count)


(n, m, k) = input().split(' ', 2)
(n, m, k) = (int(n), int(m), int(k))
lst = []
lst2 = []
graph = {}
for i in range(0, k):
	(r, c1, c2) = input().split(' ', 2)
	(r, c1, c2) = (int(r), int(c1), int(c2))
	lst.append([r - 1, c1, c2])
	graph[int(r) - 1] = []
for i in range(0, k):
	index = 0
	flag = 0
	flag2 = 0
	for j in range(0, len(graph[lst[i][0]])):
		if lst[i][1] > graph[lst[i][0]][j][0]:
			pass
		else:
			if lst[i][1] == graph[lst[i][0]][j][0]:
				graph[lst[i][0]][j][1] = max(graph[lst[i][0]][j][1], lst[i][2])
				flag2 = 1
			index = j
			flag = 1
			break
	if flag == 0:
		index = len(graph[lst[i][0]])
	if flag2 == 0:
		graph[lst[i][0]].insert(index, [lst[i][1], lst[i][2]])
for item in graph:
	j = 0
	while True:
		if j < len(graph[item]) - 1:
			if graph[item][j + 1][0] <= graph[item][j][1] + 1:
				if graph[item][j + 1][1] > graph[item][j][1]:
					graph[item][j][1] = graph[item][j + 1][1]
				graph[item].pop(j + 1)
				j -= 1
		else:
			break
		j += 1
count = 0
for item in graph:
	for j in range(0, len(graph[item])):
		count += graph[item][j][1] - graph[item][j][0] + 1
print(m * n - count)


def findlampposts(tracks, n, m):
	posts = m * n
	tracks = sorted(tracks, key=lambda x: (x[0], x[1], x[2]))
	r = 0
	cr = 0
	for t in tracks:
		if t[0] == r:
			if t[1] > cr:
				posts -= 1 + t[2] - t[1]
			elif t[2] <= cr:
				pass
			else:
				posts -= t[2] - cr
		else:
			cr = 0
			r = t[0]
			posts -= 1 + t[2] - t[1]
		if t[2] > cr:
			cr = t[2]
	return posts

def main():
	(n, m, k) = tuple([int(x) for x in input().strip().split(' ')])
	tracks = []
	for i in range(k):
		tracks.append([int(x) for x in input().strip().split(' ')])
	print('%d' % (findlampposts(tracks, n, m),))
main()


import sys
(m, n, k) = [int(i) for i in input().strip().split()]
KC1C2 = [[int(i) for i in line.strip().split()] for line in sys.stdin.readlines()]

def mergeRailSegments(allSegList):
	allSegList.sort(key=lambda x: x[0])
	nonOverlapSegmentsList = [allSegList[0]]
	for seg in allSegList[1:]:
		for i in range(len(nonOverlapSegmentsList)):
			noseg = nonOverlapSegmentsList[i]
			if seg[0] <= noseg[1]:
				newNoseg = (noseg[0], max(seg[1], noseg[1]))
				nonOverlapSegmentsList[i] = newNoseg
				break
			elif i == len(nonOverlapSegmentsList) - 1:
				nonOverlapSegmentsList.append(seg)
			else:
				continue
	return nonOverlapSegmentsList

def recurMerge(segList):
	if len(segList) == 1:
		return segList
	else:
		segList.sort(key=lambda x: x[0])
		numOverlappingSegs = sum([segList[i][1] >= segList[i + 1][0] for i in range(len(segList) - 1)])
		if numOverlappingSegs == 0:
			return segList
		else:
			mergedSegList = mergeRailSegments(segList)
			return recurMerge(mergedSegList)

def sumSegLengths(nonOverlappingSegList):
	return sum([seg[1] - seg[0] + 1 for seg in nonOverlappingSegList])
railrowSet = set([railrow[0] for railrow in KC1C2])
d = {r: [(row[1], row[2]) for row in KC1C2 if row[0] == r] for r in railrowSet}
railSquares = sum([sumSegLengths(recurMerge(d[key])) for key in d])
print(m * n - railSquares)


s1 = input().split(' ')
n = int(s1[0])
m = int(s1[1])
trains = int(s1[2])
train_info = dict()
for i in range(trains):
	char_arr = input().split(' ')
	row = int(char_arr[0])
	start = int(char_arr[1])
	end = int(char_arr[2])
	if row in train_info:
		info = train_info[row]
		for j in info:
			if j[0] <= start <= j[1] or j[0] <= end <= j[1]:
				start = min(start, j[0])
				end = max(end, j[1])
				train_info[row].remove(j)
				break
		train_info[row].append([start, end])
	else:
		train_info[row] = [[int(char_arr[1]), int(char_arr[2])]]
count = 0
for (k, v) in train_info.items():
	for j in v:
		count += j[1] - j[0] + 1
print(n * m - count)


def add(key, start, end):
	to_remove = []
	no_add = False
	for tup in row_map[key]:
		if tup[1] >= end and start <= tup[0] and (end >= tup[0]):
			end = tup[1]
			to_remove.append(tup)
		elif tup[1] <= end and start >= tup[0] and (start <= tup[1]):
			start = tup[0]
			to_remove.append(tup)
		elif start <= tup[0] and end >= tup[1]:
			to_remove.append(tup)
		elif tup[1] >= end and tup[0] <= start:
			no_add = True
	if to_remove:
		for tup in to_remove:
			row_map[key].remove(tup)
	if not no_add:
		row_map[key].append((start, end))
s_len = input().strip()
row_map = {}
x = [int(i) for i in s_len.split()]
tracks = x[2]
total = x[0] * x[1]
for i in range(tracks):
	t = input().strip()
	s = [int(i) for i in t.split()]
	try:
		row_map[s[0]]
		add(s[0], s[1], s[2])
	except KeyError:
		row_map[s[0]] = [(s[1], s[2])]
count = 0
for key in row_map:
	test = 0
	range_lis = []
	j = 0
	for tup in row_map[key]:
		range_lis.append(tup[0])
		range_lis.append(tup[1])
	range_lis = sorted(range_lis)
	for i in range(0, len(range_lis), 2):
		test += range_lis[i + 1] - range_lis[i] + 1
		count += range_lis[i + 1] - range_lis[i] + 1
ans = total - count
print(ans)


def overlapped(c1, c2, g1, g2):
	if c1 == g2 + 1 or g1 == c2 + 1:
		return True
	elif g1 <= c1 <= g2 or g1 <= c2 <= g2:
		return True
	elif c1 <= g1 <= c2 or c1 <= g2 <= c2:
		return True

def update_gridland(r, c1, c2):
	if r not in gridland:
		gridland[r] = []
		gridland[r].append((c1, c2))
	else:
		trackadded = False
		for i in range(len(gridland[r])):
			if overlapped(c1, c2, gridland[r][i][0], gridland[r][i][1]):
				gridland[r][i] = (min(c1, gridland[r][i][0]), max(c2, gridland[r][i][1]))
				trackadded = True
				break
		if not trackadded:
			gridland[r].append((c1, c2))
(n, m, k) = list(map(int, input().strip().split()))
tracks = []
for i in range(k):
	tracks.append(tuple(map(int, input().strip().split())))
tracks = tuple(tracks)
gridland = {}
for t in tracks:
	(r, c1, c2) = t
	update_gridland(r, c1, c2)
used = 0
for row in gridland:
	for tracks in gridland[row]:
		used += abs(tracks[0] - tracks[1]) + 1
print(n * m - used)