solutions: ["from collections import defaultdict\n(n, m, k) = map(int, input().split())\ntracks = defaultdict(list)\nfor _ in range(k):\n\t(row, c1, c2) = map(int, input().split())\n\ttracks[row].append((c1, -1))\n\ttracks[row].append((c2 + 1, 1))\nans = 0\nfor row in tracks:\n\ttracks[row].sort()\n\tprev = tracks[row][0][0]\n\tdepth = 1\n\tfor event in tracks[row][1:]:\n\t\tif depth > 0:\n\t\t\tans += event[0] - prev\n\t\tdepth -= event[1]\n\t\tprev = event[0]\nprint(n * m - ans)\n", "(n, m, k) = map(int, input().split())\nrow_tracks = {}\nfor i in range(k):\n\t(r, c1, c2) = map(int, input().split())\n\tif r not in row_tracks:\n\t\trow_tracks[r] = []\n\trow_tracks[r].append((c1, c2))\ntotal_occuppied = 0\nfor r in row_tracks:\n\trow_tracks[r].sort()\n\tcurrent_occuppied = 0\n\tcurrent_c2 = 0\n\tfor track in row_tracks[r]:\n\t\t(c1, c2) = track\n\t\tif c1 <= current_c2:\n\t\t\tif c2 > current_c2:\n\t\t\t\tcurrent_occuppied += c2 - current_c2\n\t\telse:\n\t\t\tcurrent_occuppied += c2 - c1 + 1\n\t\tcurrent_c2 = max(current_c2, c2)\n\ttotal_occuppied += current_occuppied\nprint(n * m - total_occuppied)\n", "(n, m, k) = [int(x) for x in input().split()]\ntracks = {}\ntaken = 0\nfor i in range(k):\n\t(r, c1, c2) = [int(x) for x in input().split()]\n\tl = c2 - c1 + 1\n\trow = tracks[r] if r in tracks else []\n\tfor t in row:\n\t\tif c1 >= t[0] and c1 <= t[1]:\n\t\t\tc1 = t[1] + 1\n\t\tif c2 >= t[0] and c2 <= t[1]:\n\t\t\tc2 = t[0] - 1\n\t\tl = max(c2 - c1 + 1, 0)\n\t\tif l == 0:\n\t\t\tbreak\n\tif l > 0:\n\t\trow.append((c1, c2))\n\t\ttracks[r] = row\n\t\ttaken += l\nprint(n * m - taken)\n", "(N, M, K) = map(int, input().split())\nD = {}\nfor k in range(K):\n\t(r, c1, c2) = map(int, input().split())\n\tif r not in D.keys():\n\t\tD[r] = []\n\tD[r] += [[c1, 1], [c2, -1]]\nemptyFields = 0\nfor r in D.keys():\n\tX = {}\n\tfor T in D[r]:\n\t\tif T[0] in X.keys():\n\t\t\tX[T[0]] += T[1]\n\t\telse:\n\t\t\tX[T[0]] = T[1]\n\tL = sorted(list(X.keys()))\n\ttrains = 0\n\tfor i in range(0, len(L)):\n\t\tif i == 0:\n\t\t\temptyFields += L[0] - 1\n\t\telif trains == 0:\n\t\t\temptyFields += L[i] - L[i - 1] - 1\n\t\ttrains += X[L[i]]\n\temptyFields += M - L[-1]\nemptyFields += (N - len(D.keys())) * M\nprint(emptyFields)\n", "import sys\n(n, m, k) = (int(x) for x in sys.stdin.readline().split())\ntracks = {}\nfor _ in range(k):\n\t(r, c1, c2) = (int(x) for x in sys.stdin.readline().split())\n\tts = tracks.get(r, [])\n\tif len(ts) == 0:\n\t\tts.append((c1, c2))\n\telse:\n\t\ti = 0\n\t\tj = len(ts) - 1\n\t\twhile j >= 0 and ts[j][1] >= c1:\n\t\t\tj -= 1\n\t\twhile i < len(ts) and ts[i][0] <= c2:\n\t\t\ti += 1\n\t\tif j == len(ts) - 1:\n\t\t\tts.append((c1, c2))\n\t\telif i == 0:\n\t\t\tts = [(c1, c2)] + ts\n\t\telse:\n\t\t\tc1 = min(c1, ts[j + 1][0])\n\t\t\tc2 = max(c2, ts[i - 1][1])\n\t\t\tts = ts[:j + 1] + [(c1, c2)] + ts[i:]\n\ttracks[r] = ts\nresult = n * m\nfor r in tracks:\n\tfor t in tracks[r]:\n\t\tresult -= t[1] - t[0] + 1\nprint(result)\n", "(n, m, k) = [int(v) for v in input().split(' ')]\ntrain_tracks = []\nfor t in range(k):\n\ttrain_tracks.append([int(v) for v in input().split(' ')])\nlamp = n * m\ni = 0\ntrain_tracks.sort()\nwhile i < len(train_tracks) - 1:\n\tif train_tracks[i][0] == train_tracks[i + 1][0]:\n\t\tif train_tracks[i + 1][1] <= train_tracks[i][2]:\n\t\t\ttrain_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])]\n\t\t\ttrain_tracks.pop(i + 1)\n\t\telse:\n\t\t\ti += 1\n\telse:\n\t\ti += 1\nfor t in train_tracks:\n\tlamp -= t[2] - t[1] + 1\nprint(lamp)\n", "from collections import defaultdict\n(n, m, k) = map(int, input().split())\ncounter = defaultdict(list)\nfor _ in range(k):\n\t(r, c, d) = map(int, input().split())\n\tcounter[r].append([c, d])\nres = n * m\nfor x in counter.values():\n\tx.sort()\n\t(pos, cur) = (0, 1)\n\twhile cur != len(x):\n\t\tif x[cur][0] <= x[pos][1]:\n\t\t\tx[pos][1] = max(x[pos][1], x[cur][1])\n\t\t\tx.pop(cur)\n\t\telse:\n\t\t\t(pos, cur) = (cur, cur + 1)\n\tres -= sum(map(lambda i: i[1] - i[0] + 1, x))\nprint(res)\n", "import sys\n(row, col, k) = map(int, input().split())\ndic = {}\nif k == 0:\n\tprint(row * col)\n\tsys.exit()\nfor i in range(k):\n\t(r, c1, c2) = map(int, input().split())\n\tif r not in dic:\n\t\tdic[r] = []\n\t_ = (c1, c2)\n\tdic[r].append(_)\ntotal = row * col\nfor i in dic:\n\tsize = len(dic[i])\n\tx = dic[i]\n\tx.sort()\n\tstart = x[0][0]\n\tend = x[0][1]\n\tfor j in range(1, size):\n\t\tif x[j][0] > end:\n\t\t\ttotal -= end - start + 1\n\t\t\tstart = x[j][0]\n\t\t\tend = x[j][1]\n\t\telif x[j][1] > end:\n\t\t\tend = x[j][1]\n\ttotal -= end - start + 1\nprint(total)\n", "from collections import defaultdict\n\ndef r():\n\treturn list(map(int, input().split()))\n\ndef ri():\n\treturn int(input())\n\ndef main():\n\t(n, m, k) = r()\n\ttracks = defaultdict(list)\n\toccupied = 0\n\tfor _ in range(k):\n\t\t(row, c1, c2) = r()\n\t\ttracks[row].append((c1, c2 + 1))\n\tfor row in tracks:\n\t\ttracks[row].sort()\n\t\tcur_hi = -1\n\t\tfor (lo, hi) in tracks[row]:\n\t\t\tlo = max(cur_hi, lo)\n\t\t\toccupied += max(0, hi - lo)\n\t\t\tcur_hi = max(hi, cur_hi)\n\tprint(n * m - occupied)\nmain()\n", "from collections import defaultdict\n(N, M, K) = map(int, input().split())\nrows = defaultdict(list)\nfor _ in range(K):\n\t(r, c1, c2) = map(int, input().split())\n\trows[r].append((c1, c2))\nans = N * M\nfor k in rows.keys():\n\trows[k].sort()\nfor row in rows.values():\n\tend = 0\n\tfor (c1, c2) in row:\n\t\tif end < c1:\n\t\t\tans -= c2 - c1 + 1\n\t\telif c1 <= end < c2:\n\t\t\tans -= c2 - end\n\t\tend = max(end, c2)\nprint(ans)\n", "(d1, d2, k) = list(map(int, input().split()))\ncoords = [list(map(int, input().split())) for _ in range(k)]\ncoords = sorted(coords, key=lambda x: x[0])\nm = {}\nfor c in coords:\n\trow = c[0]\n\tc1 = min(c[1], c[2])\n\tc2 = max(c[1], c[2])\n\tif row in m:\n\t\tm[row] = m[row] + [[c1, c2]]\n\telse:\n\t\tm[row] = [[c1, c2]]\nm2 = []\nfor (k, v) in m.items():\n\tr = []\n\tfor current in v:\n\t\tfor stored in r:\n\t\t\tif not current or current[0] > current[1]:\n\t\t\t\tbreak\n\t\t\tif not stored or stored[0] > stored[1]:\n\t\t\t\tcontinue\n\t\t\tif current[0] >= stored[0] and current[1] <= stored[1]:\n\t\t\t\tcurrent = None\n\t\t\t\tbreak\n\t\t\tif stored[0] >= current[0] and stored[1] <= current[1]:\n\t\t\t\tstored[1] = stored[0] - 1\n\t\t\t\tcontinue\n\t\t\tif current[0] < stored[0] and current[1] >= stored[0]:\n\t\t\t\tcurrent[1] = stored[0] - 1\n\t\t\tif current[1] > stored[1] and current[0] <= stored[1]:\n\t\t\t\tcurrent[0] = stored[1] + 1\n\t\tif current and current[0] <= current[1]:\n\t\t\tl = current[:]\n\t\t\tr.append(l)\n\t\t\tm2.append(l)\nm2 = [x for x in m2 if x and x[1] >= x[0]]\nocc = sum([x[1] - x[0] + 1 for x in m2])\ntotal = d1 * d2 - occ\nprint(total)\n", "def intersect(a, c):\n\t(a1, a2) = a\n\t(c1, c2) = c\n\tif max(a1, c1) <= min(a2, c2):\n\t\treturn [[min(a1, c1), max(a2, c2)]]\n\telse:\n\t\treturn [a, c]\n(n, m, k) = [int(x) for x in input().split()]\nrows = {}\nres = n * m\nfor i in range(k):\n\t(r, c1, c2) = [int(x) for x in input().split()]\n\tif r in rows:\n\t\trows[r].append([c1, c2])\n\telse:\n\t\trows[r] = [[c1, c2]]\nfor r in rows:\n\trow = rows[r]\n\tsorted(row, key=lambda path: path[0])\n\tnew_row = [row[0]]\n\tfor i in range(1, len(row)):\n\t\tlast_proc_path = new_row[-1]\n\t\tnew_row = new_row[:-1]\n\t\tunproc_path = row[i]\n\t\tnew_row += intersect(last_proc_path, unproc_path)\n\tfor i in range(len(new_row)):\n\t\tres -= new_row[i][1] - new_row[i][0] + 1\nprint(res)\n", "(m, n, k) = map(int, input().split())\nres = 0\nd = {}\nfor _ in range(k):\n\t(a, b, c) = map(int, input().split())\n\tif not a in d:\n\t\td[a] = []\n\td[a].append((b, 1))\n\td[a].append((c, -1))\nfor (r, ts) in d.items():\n\tc = 0\n\tlast = 0\n\tts = sorted(ts)\n\tfor i in range(len(ts)):\n\t\tt = ts[i]\n\t\tif c != 0:\n\t\t\tif c + t[1] == 0:\n\t\t\t\tres += t[0] - last + (1 if i == len(ts) - 1 or ts[i + 1][0] != t[0] else 0)\n\t\tif c == 0:\n\t\t\tlast = t[0]\n\t\tc += t[1]\nprint(m * n - res)\n", "(n, m, k) = [int(x) for x in input().strip().split(' ')]\ntracks = {}\nfor _ in range(k):\n\t(r, c1, c2) = [int(x) for x in input().strip().split(' ')]\n\ttracks.setdefault(r, []).append((c1, c2))\nlamps = n * m\nfor r in tracks:\n\tpairs = tracks[r]\n\tpairs.sort()\n\tmerged = [pairs[0]]\n\tfor (c1, c2) in pairs[1:]:\n\t\tif c1 > merged[0][1]:\n\t\t\tmerged.insert(0, (c1, c2))\n\t\telse:\n\t\t\tnew_c1 = merged[0][0]\n\t\t\tnew_c2 = max(merged[0][1], c2)\n\t\t\tmerged[0] = (new_c1, new_c2)\n\ttaken = sum(map(lambda pair: pair[1] - pair[0] + 1, merged))\n\tlamps -= taken\nprint(lamps)\n", "def mark_tracks(tracks, r, c1, c2):\n\tif r not in tracks:\n\t\ttracks[r] = []\n\ttracks[r].append((c1, c2))\n\ndef delete_overlapped_tracks(tracks):\n\tfor r in tracks.keys():\n\t\tnew_tracks_in_row = []\n\t\ttracks_in_row = sorted(tracks[r])\n\t\t(start, end) = tracks_in_row[0]\n\t\tfor track in tracks_in_row:\n\t\t\tif track[0] >= start and track[0] <= end:\n\t\t\t\tend = max(end, track[1])\n\t\t\telse:\n\t\t\t\tnew_tracks_in_row.append((start, end))\n\t\t\t\t(start, end) = track\n\t\tnew_tracks_in_row.append((start, end))\n\t\ttracks[r] = new_tracks_in_row\n\ndef count_tracks(tracks):\n\tnum = 0\n\tfor (r, tracks_in_row) in tracks.items():\n\t\tfor track in tracks_in_row:\n\t\t\tnum += track[1] - track[0] + 1\n\treturn num\n(n, m, k) = input().strip().split(' ')\n(n, m, k) = (int(n), int(m), int(k))\ntracks = {}\nfor _ in range(k):\n\t(r, c1, c2) = input().strip().split(' ')\n\t(r, c1, c2) = (int(r), int(c1), int(c2))\n\tmark_tracks(tracks, r, c1, c2)\ndelete_overlapped_tracks(tracks)\nprint(n * m - count_tracks(tracks))\n", "import math\n(n, m, k) = list(map(int, input().split()))\ntracks = {}\ntrackCount = {}\nfor i in range(k):\n\t(r, s, e) = list(map(int, input().split()))\n\tif s > e:\n\t\t(s, e) = (e, s)\n\tif r in tracks.keys():\n\t\tfor (x, y) in tracks[r]:\n\t\t\tif x <= s and y >= e:\n\t\t\t\t(s, e) = (-1, -2)\n\t\t\telif x <= s and y >= s:\n\t\t\t\ts = y + 1\n\t\t\telif x <= e and y >= e:\n\t\t\t\te = x - 1\n\t\tif e >= s:\n\t\t\ttracks[r].append((s, e))\n\t\t\ttrackCount[r] += e - s + 1\n\telse:\n\t\ttracks[r] = [(s, e)]\n\t\ttrackCount[r] = e - s + 1\nans = 0\nfor i in trackCount.keys():\n\tans += trackCount[i]\nprint(n * m - ans)\n", "(N, M, K) = map(int, input().split())\nrail = {}\nfor _ in range(K):\n\t(r, f, t) = map(int, input().split())\n\tif r not in rail:\n\t\trail[r] = []\n\trail[r].append((t, f))\ncovered = 0\nfor x in rail:\n\trail[x].sort()\n\tprv = (-1, -2)\n\tfor p in rail[x]:\n\t\tp = (p[1], p[0])\n\t\tif p[0] <= prv[1]:\n\t\t\ttmp = min(prv[0], p[0])\n\t\t\ttmp2 = max(prv[1], p[1])\n\t\t\tprv = (tmp, tmp2)\n\t\telse:\n\t\t\tcovered += prv[1] - prv[0] + 1\n\t\t\tprv = p\n\tcovered += prv[1] - prv[0] + 1\nans = N * M - covered\nprint(ans)\n", "import collections\n(m, n, k) = [int(x) for x in input().split()]\ncnt = m * n\nd = collections.defaultdict(lambda : [])\nfor i in range(k):\n\t(r, c1, c2) = [int(x) for x in input().split()]\n\tif c2 < c1:\n\t\t(c1, c2) = (c2, c1)\n\td[r].append((c1, c2))\nfor r in d:\n\tfin = []\n\tl = d[r]\n\tl.sort()\n\ttod = set()\n\tfor i in range(len(l)):\n\t\tr1 = l[i][1]\n\t\tif i in tod:\n\t\t\tcontinue\n\t\tfor k in range(i + 1, len(l)):\n\t\t\tif k in tod:\n\t\t\t\tcontinue\n\t\t\tif l[k][0] <= r1:\n\t\t\t\tr1 = max(l[k][1], r1)\n\t\t\t\ttod.add(k)\n\t\t\telse:\n\t\t\t\tbreak\n\t\tfin.append((l[i][0], r1))\n\tfor (l1, r1) in fin:\n\t\tcnt -= r1 - l1 + 1\nprint(cnt)\n", "(n, m, k) = [int(i) for i in input().split(' ')]\nocc = 0\ntracks = list()\nfor i in range(k):\n\ttracks.append([int(i) for i in input().split(' ')])\nwhile len(tracks) > 0:\n\ttmp = list()\n\ttmp.append(tracks.pop(0))\n\tv = tmp[0][0]\n\tpos = 0\n\twhile pos < len(tracks):\n\t\tif tracks[pos][0] == v:\n\t\t\ttmp.append(tracks.pop(pos))\n\t\telse:\n\t\t\tpos = pos + 1\n\ttmp.sort(key=lambda x: x[1])\n\ttm = tmp.pop(0)\n\twhile len(tmp) > 0:\n\t\tte = tmp.pop(0)\n\t\tif te[1] <= tm[2]:\n\t\t\ttm[2] = max(te[2], tm[2])\n\t\telse:\n\t\t\tocc = occ + tm[2] - tm[1] + 1\n\t\t\ttm = te\n\tocc = occ + tm[2] - tm[1] + 1\nprint(n * m - occ)\n", "import heapq\n\ndef get_points(s):\n\ti = 0\n\twhile i < len(s) - 1:\n\t\tif s[i][0] <= s[i + 1][0] <= s[i][1]:\n\t\t\tnew_point = (s[i][0], max(s[i][1], s[i + 1][1]))\n\t\t\ts[i:i + 2] = [new_point]\n\t\telse:\n\t\t\ti += 1\n\tnum_points = 0\n\tfor (a, b) in s:\n\t\tnum_points += b - a + 1\n\treturn num_points\n(n, m, k, *_) = map(int, input().split())\nS = {}\nfor _ in range(k):\n\t(r, c1, c2, *_) = map(int, input().split())\n\theapq.heappush(S.setdefault(r, []), (c1, c2))\nnum_lampposts = m * n\nfor e in S.values():\n\th = [heapq.heappop(e) for _ in range(len(e))]\n\tnum_lampposts -= get_points(h)\nprint(num_lampposts)\n", "def merge(intervals):\n\tsorted_by_lower_bound = sorted(intervals, key=lambda tup: tup[0])\n\tmerged = []\n\tfor higher in sorted_by_lower_bound:\n\t\tif not merged:\n\t\t\tmerged.append(higher)\n\t\telse:\n\t\t\tlower = merged[-1]\n\t\t\tif higher[0] <= lower[1]:\n\t\t\t\tupper_bound = max(lower[1], higher[1])\n\t\t\t\tmerged[-1] = (lower[0], upper_bound)\n\t\t\telse:\n\t\t\t\tmerged.append(higher)\n\treturn merged\n(n, m, k) = map(int, input().split())\nd = {}\nfor i in range(k):\n\t(r, c1, c2) = map(int, input().split())\n\tif r not in d:\n\t\td[r] = []\n\td[r].append((c1, c2))\nfor r in d:\n\td[r] = merge(d[r])\nans = n * m\nfor i in d:\n\tfor t in d[i]:\n\t\tans -= t[1] - t[0] + 1\nprint(ans)\n", "(n, m, k) = [int(x) for x in input().split(' ')]\nfrom collections import defaultdict\ngrid = defaultdict(list)\nfor _ in range(k):\n\t(r, c1, c2) = [int(x) for x in input().split(' ')]\n\tg = grid[r]\n\tgx = []\n\ti = 0\n\twhile i < len(g) and g[i + 1] < c1:\n\t\tgx.extend([g[i], g[i + 1]])\n\t\ti += 2\n\tif i == len(g):\n\t\tgrid[r] = gx + [c1, c2]\n\t\tcontinue\n\tgx.append(min(g[i], c1))\n\twhile i < len(g) and g[i + 1] < c2:\n\t\ti += 2\n\tif i == len(g):\n\t\tgrid[r] = gx + [c2]\n\t\tcontinue\n\tif g[i] > c2:\n\t\tgx.append(c2)\n\telse:\n\t\tgx.append(g[i + 1])\n\t\ti += 2\n\twhile i < len(g):\n\t\tgx.extend([g[i], g[i + 1]])\n\t\ti += 2\n\tgrid[r] = gx\nlamp = m * n\nfor r in grid:\n\tg = grid[r]\n\tfor i in range(0, len(g), 2):\n\t\tlamp -= g[i + 1] + 1 - g[i]\nprint(lamp)\n", "from collections import defaultdict\n(n, m, k) = input().split(' ')\n(n, m, k) = (int(n), int(m), int(k))\n\ndef merge_intervals(lista):\n\tn = len(lista)\n\tlista.sort(key=lambda element: (element[0], element[1]), reverse=True)\n\tindex = 0\n\tfor i in range(n):\n\t\tif index and lista[index - 1][0] <= lista[i][1]:\n\t\t\twhile index and lista[index - 1][0] <= lista[i][1]:\n\t\t\t\tlista[index - 1][1] = max(lista[index - 1][1], lista[i][1])\n\t\t\t\tlista[index - 1][0] = min(lista[index - 1][0], lista[i][0])\n\t\t\t\tindex -= 1\n\t\telse:\n\t\t\tlista[index] = lista[i]\n\t\tindex += 1\n\treturn lista[0:index]\n\ndef calcula_linha(lista):\n\ts = 0\n\tfor l in lista:\n\t\ts += l[1] - l[0]\n\treturn s\nn_post = n * m\npost_locations = defaultdict(list)\nfor i in range(k):\n\t(r, c1, c2) = input().split(' ')\n\t(r, c1, c2) = (int(r), int(c1), int(c2))\n\tpost_locations[r].append([c1, c2 + 1])\n\tpost_locations[r] = merge_intervals(post_locations[r])\ncounter = 0\nfor (key, value) in post_locations.items():\n\tcounter += calcula_linha(value)\nprint(n_post - counter)\n", "(N, M, K) = [int(i) for i in input().split()]\nd = {}\nfor k in range(K):\n\tl = [int(i) for i in input().split()]\n\tif l[0] in d:\n\t\td[l[0]] = sorted(d[l[0]] + [(l[1], l[2])], key=lambda k: k[1])\n\t\td[l[0]] = sorted(d[l[0]] + [(l[1], l[2])], key=lambda k: k[0])\n\telse:\n\t\td[l[0]] = [(l[1], l[2])]\ncnt = N * M\nfor i in d:\n\tx = [k[0] for k in d[i]]\n\ty = [k[1] for k in d[i]]\n\tcnt -= y[0] - x[0] + 1\n\tfor j in range(1, len(x)):\n\t\tif x[j] <= max(y[:j]):\n\t\t\tif y[j] > max(y[:j]):\n\t\t\t\tcnt -= y[j] - max(y[:j])\n\t\telif x[j] > max(y[:j]):\n\t\t\tcnt -= y[j] - x[j] + 1\nprint(cnt)\n", "def calcualate(array):\n\ti = 0\n\tcount = 0\n\tresult = [array[0]]\n\tfor i in range(1, len(array)):\n\t\tstart = result.pop(-1)\n\t\tif start[1] >= array[i][0]:\n\t\t\tresult.append((start[0], max(start[1], array[i][1])))\n\t\telse:\n\t\t\tresult.append(start)\n\t\t\tresult.append(array[i])\n\tfor each in result:\n\t\tcount += each[1] - each[0] + 1\n\treturn count\n(n, m, k) = map(int, input().split())\ncount = 0\nmy_hash = {}\nfor i in range(k):\n\t(r, c1, c2) = map(int, input().split())\n\tif r not in my_hash:\n\t\tmy_hash[r] = [(c1, c2)]\n\telse:\n\t\tmy_hash[r].append((c1, c2))\nfor each in my_hash:\n\tmy_hash[each].sort(key=lambda x: x[0])\n\tcount += calcualate(my_hash[each])\nprint(n * m - count)\n", "def range_overlap_adjust(list_ranges):\n\toverlap_corrected = []\n\tfor (start, stop) in sorted(list_ranges):\n\t\tif overlap_corrected and start - 1 <= overlap_corrected[-1][1] and (stop >= overlap_corrected[-1][1]):\n\t\t\toverlap_corrected[-1] = (min(overlap_corrected[-1][0], start), stop)\n\t\telif overlap_corrected and start <= overlap_corrected[-1][1] and (stop <= overlap_corrected[-1][1]):\n\t\t\tbreak\n\t\telse:\n\t\t\toverlap_corrected.append((start, stop))\n\treturn overlap_corrected\n\ndef merge_trains3(arr):\n\tb = range_overlap_adjust(arr)\n\tsumma = 0\n\tfor i in b:\n\t\tsumma += i[1] + 1 - i[0]\n\treturn summa\n\ndef merge_trains(arr):\n\ts = set()\n\tfor i in arr:\n\t\ts = s.union(set(range(i[0], i[1] + 1)))\n\treturn len(s)\n\ndef merge_trains2(arr):\n\tb = []\n\tfor (begin, end) in sorted(arr):\n\t\tif b and b[-1][1] >= begin - 1:\n\t\t\tb[-1][1] = max(b[-1][1], end)\n\t\telse:\n\t\t\tb.append([begin, end])\n\tsumma = 0\n\tfor i in b:\n\t\tsumma += i[1] + 1 - i[0]\n\treturn summa\n(n, m, k) = [int(i) for i in input().strip().split()]\nlamp_posts = n * m\ntrain_dict = {}\nfor train in range(k):\n\tstri = [int(j) for j in input().strip().split()]\n\trow = stri[0]\n\tif row in train_dict.keys():\n\t\ttrain_dict[row].append(stri[1:])\n\telse:\n\t\ttrain_dict[row] = [stri[1:]]\nfor (key, value) in train_dict.items():\n\tlamp_posts -= merge_trains2(value)\nprint(lamp_posts)\n", "import itertools\n(n, m, k) = map(int, input().strip().split())\ntracks = []\nfor i in range(0, k):\n\t(r, c1, c2) = map(int, input().strip().split())\n\ttracks.append([r, c1, c2])\ntracks.sort()\nfor i in range(0, len(tracks)):\n\tj = i + 1\n\twhile j < len(tracks):\n\t\tif tracks[i][0] == tracks[j][0] and tracks[i][2] >= tracks[j][1]:\n\t\t\ttracks[i][1] = min(tracks[i][1], tracks[j][1])\n\t\t\ttracks[i][2] = max(tracks[i][2], tracks[j][2])\n\t\t\ttracks.pop(j)\n\t\telse:\n\t\t\tj += 1\ncount = n * m - sum([track[2] - track[1] + 1 for track in tracks])\nprint(count)\n", "def main():\n\t(nrows, ncols, ntracks) = readints()\n\ttrack = {}\n\tfor _ in range(ntracks):\n\t\t(r, c1, c2) = readints()\n\t\tif r not in track:\n\t\t\ttrack[r] = ([c1], [c2])\n\t\telse:\n\t\t\tt = track[r]\n\t\t\tt[0].append(c1)\n\t\t\tt[1].append(c2)\n\ttcount = 0\n\tfor t in track.values():\n\t\ttcount += counttrack(*t)\n\tprint(nrows * ncols - tcount)\n\ndef readints():\n\treturn [int(fld) for fld in input().strip().split()]\n\ndef counttrack(start, stop):\n\tstart = sorted(start) + [1 + max(stop)]\n\tstop = sorted(stop)\n\tans = trackness = istart = istop = 0\n\twhile istop < len(stop):\n\t\tif start[istart] <= stop[istop]:\n\t\t\tif trackness == 0:\n\t\t\t\tstarttrack = start[istart]\n\t\t\ttrackness += 1\n\t\t\tistart += 1\n\t\telse:\n\t\t\ttrackness -= 1\n\t\t\tif trackness == 0:\n\t\t\t\tans += stop[istop] - starttrack + 1\n\t\t\tistop += 1\n\treturn ans\nmain()\n", "def getTrackLength(tracks):\n\ttracks = sorted(tracks)\n\tstart = tracks[0][0]\n\tend = tracks[0][1]\n\tif len(tracks) == 1:\n\t\treturn end - start + 1\n\tnew_tracks = []\n\tfor i in range(1, len(tracks)):\n\t\ts = tracks[i][0]\n\t\te = tracks[i][1]\n\t\tif s <= end:\n\t\t\tif e > end:\n\t\t\t\tend = e\n\t\telse:\n\t\t\tnew_tracks.append((start, end))\n\t\t\tstart = s\n\t\t\tend = e\n\tnew_tracks.append((start, end))\n\tcount = 0\n\tfor track in new_tracks:\n\t\tcount += track[1] - track[0] + 1\n\treturn count\n(n, m, k) = map(int, input().strip().split())\nrow_track_dict = {}\nfor i in range(k):\n\t(row, start, end) = map(int, input().strip().split())\n\tif row not in row_track_dict.keys():\n\t\trow_track_dict[row] = [(start, end)]\n\telse:\n\t\trow_track_dict[row].append((start, end))\ntotal_col_used = 0\nfor tracks in row_track_dict.values():\n\ttotal_col_used += getTrackLength(tracks)\nprint(n * m - total_col_used)\n", "(m, n, t) = [int(x) for x in input().split()]\nd = {}\nfor i in range(t):\n\t(r, c1, c2) = [int(x) for x in input().split()]\n\tif r in d:\n\t\tlower = 0\n\t\tupper = 0\n\t\tll = False\n\t\tul = False\n\t\tfor j in range(len(d[r])):\n\t\t\tif c1 >= d[r][j][0] and c1 <= d[r][j][1] + 1:\n\t\t\t\tll = True\n\t\t\t\tlower = j\n\t\t\t\tbreak\n\t\tfor j in range(len(d[r])):\n\t\t\tif c2 >= d[r][j][0] - 1 and c2 <= d[r][j][1] + 1:\n\t\t\t\tul = True\n\t\t\t\tupper = j\n\t\tif ll == True:\n\t\t\tif ul == True:\n\t\t\t\td[r][lower:upper + 1] = [[min(d[r][lower][0], c1), max(d[r][upper][1], c2)]]\n\t\t\telse:\n\t\t\t\td[r][lower:lower + 1] = [[min(d[r][lower][0], c1), c2]]\n\t\telif ul == True:\n\t\t\td[r][upper:upper + 1] = [[c1, max(d[r][upper][1], c2)]]\n\t\telse:\n\t\t\twrap = False\n\t\t\tfor k in range(len(d[r])):\n\t\t\t\tif d[r][k][0] > c1 and d[r][k][1] < c2:\n\t\t\t\t\twrap = True\n\t\t\t\t\td[r][k] = [c1, c2]\n\t\t\t\t\tbreak\n\t\t\tif not wrap:\n\t\t\t\td[r].append([c1, c2])\n\t\td[r].sort(key=lambda x: x[0])\n\telse:\n\t\td[r] = [[c1, c2]]\nt = m * n\nfor i in d:\n\tfor j in d[i]:\n\t\tt -= j[1] - j[0] + 1\nprint(t)\n", "(n, m, k) = [int(x) for x in input().split()]\ntrack = {}\nfor i in range(k):\n\t(r, c1, c2) = [int(x) for x in input().split()]\n\ttemp = track.get(r, [])\n\tif len(temp) == 0:\n\t\ttemp.append((c1, c2))\n\t\ttrack[r] = temp\n\telse:\n\t\tj = 0\n\t\tf = True\n\t\twhile j < len(temp):\n\t\t\tt = temp[j]\n\t\t\tif c2 < t[0] - 1:\n\t\t\t\ttemp.insert(j, (c1, c2))\n\t\t\t\tbreak\n\t\t\telif c2 >= t[0] - 1 and c2 <= t[1]:\n\t\t\t\tif c1 >= t[0]:\n\t\t\t\t\tbreak\n\t\t\t\ttemp[j] = (c1, t[1])\n\t\t\t\tbreak\n\t\t\telif c1 >= t[0] and c1 <= t[1] + 1:\n\t\t\t\tif c2 <= t[1]:\n\t\t\t\t\tbreak\n\t\t\t\tc1 = t[0]\n\t\t\t\ttemp.pop(j)\n\t\t\telse:\n\t\t\t\tj += 1\n\t\tif j >= len(temp):\n\t\t\ttemp.insert(j, (c1, c2))\nce = 0\nfor k in track:\n\trow = track.get(k)\n\tfor x in row:\n\t\tce += x[1] - x[0] + 1\nprint(n * m - ce)\n", "import sys\n(n, m, k) = input().strip().split()\n(n, m, k) = (int(n), int(m), int(k))\ntrains = {}\nfor i in range(k):\n\t(r, c1, c2) = input().strip().split()\n\t(r, c1, c2) = (int(r), min(int(c1), int(c2)), max(int(c1), int(c2)))\n\tnewRow = [[c1, c2]]\n\tif r in trains:\n\t\tfor t in trains[r]:\n\t\t\tif c1 <= t[1] and t[0] <= c2:\n\t\t\t\tnewRow[0] = [min(c1, t[0]), max(c2, t[1])]\n\t\t\telse:\n\t\t\t\tnewRow.append(t)\n\ttrains[r] = newRow\ntotal = n * m\nfor row in trains:\n\tfor t in trains[row]:\n\t\ttotal -= t[1] - t[0] + 1\nprint(total)\n", "(n, m, k) = map(int, input().strip().split())\nrows = {}\nfor _ in range(k):\n\t(r, c0, c1) = map(int, input().strip().split())\n\ttodelete = []\n\tif r in rows:\n\t\trow = rows[r]\n\t\tfor t in row:\n\t\t\tif c1 >= t[0] and c0 <= t[1]:\n\t\t\t\ttodelete.append(t)\n\t\t\t\tc0 = min(c0, t[0])\n\t\t\t\tc1 = max(c1, t[1])\n\t\tfor t in todelete:\n\t\t\trow.remove(t)\n\t\trow.append((c0, c1))\n\telse:\n\t\trows[r] = [(c0, c1)]\ntotal = n * m\nfor r in rows:\n\tfor t in rows[r]:\n\t\ttotal -= t[1] - t[0] + 1\nprint(total)\n", "(n, m, k) = tuple(map(int, input().split()))\ndic = {}\nfor i in range(k):\n\t(r, c1, c2) = tuple(map(int, input().split()))\n\tif r not in dic:\n\t\tdic[r] = {}\n\tif c1 not in dic[r]:\n\t\tdic[r][c1] = 0\n\tif c2 + 1 not in dic[r]:\n\t\tdic[r][c2 + 1] = 0\n\tdic[r][c1] = dic[r][c1] + 1\n\tdic[r][c2 + 1] = dic[r][c2 + 1] - 1\nres = 0\nfor r in dic:\n\ttracks = dic[r]\n\tkeys = tracks.keys()\n\tkeys = sorted(keys)\n\tst = 0\n\tnow = 0\n\tfor col in keys:\n\t\tif now > 0:\n\t\t\tres = res + col - st\n\t\tnow = now + tracks[col]\n\t\tst = col\nprint(n * m - res)\n", "def rem(r):\n\tlenr = len(r)\n\tif lenr == 1:\n\t\tt = r[0]\n\t\treturn t[1] - t[0] + 1\n\tx = 0\n\tr.sort()\n\t(m, lenm) = ([], 0)\n\tm0 = -1\n\tfor t in r:\n\t\tif t[0] == m0:\n\t\t\tif m[lenm - 1][1] < t[1]:\n\t\t\t\tm[lenm - 1][1] = t[1]\n\t\telse:\n\t\t\tm.append(t)\n\t\t\tlenm += 1\n\t\t\tm0 = t[0]\n\tfor i in range(0, lenm - 1):\n\t\tif m[i][1] >= m[i + 1][0]:\n\t\t\tm[i + 1][0] = m[i][0]\n\t\t\tm[i + 1][1] = max(m[i][1], m[i + 1][1])\n\t\t\tm[i][0] = -1\n\tfor i in range(0, lenm):\n\t\tif m[i][0] != -1:\n\t\t\tx += m[i][1] - m[i][0] + 1\n\treturn x\n(n, m, k) = map(int, input().strip().split(' '))\nT = []\nfor i in range(0, k):\n\t(r, c1, c2) = map(int, input().strip().split(' '))\n\tT.append([r, c1, c2])\nlent = len(T)\nans = n * m\nif lent == 0:\n\tprint(ans)\nelif lent == 1:\n\tans -= T[0][2] - T[0][2] + 1\n\tprint(ans)\nelse:\n\tT.sort()\n\tR = []\n\ti = 0\n\twhile True:\n\t\trow = [T[i][1:]]\n\t\tif i == lent - 1:\n\t\t\tR.append(row)\n\t\t\tbreak\n\t\twhile T[i][0] == T[i + 1][0]:\n\t\t\trow.append(T[i + 1][1:])\n\t\t\ti += 1\n\t\t\tif i == lent - 1:\n\t\t\t\tbreak\n\t\tR.append(row)\n\t\ti += 1\n\t\tif i == lent:\n\t\t\tbreak\n\tfor row in R:\n\t\ty = rem(row)\n\t\tans -= y\n\tprint(ans)\n", "def get_intervals(intervals):\n\tsorted_by_lower_bound = sorted(intervals, key=lambda tup: tup[0])\n\tmerged = []\n\tfor higher in sorted_by_lower_bound:\n\t\tif not merged:\n\t\t\tmerged.append(higher)\n\t\telse:\n\t\t\tlower = merged[-1]\n\t\t\tif higher[0] <= lower[1]:\n\t\t\t\tupper_bound = max(lower[1], higher[1])\n\t\t\t\tmerged[-1] = (lower[0], upper_bound)\n\t\t\telse:\n\t\t\t\tmerged.append(higher)\n\treturn merged\n\ndef test():\n\t(n, m, k) = map(int, input().split())\n\tlines = {}\n\tfor _ in range(k):\n\t\t(r, c1, c2) = map(int, input().split())\n\t\tif r not in lines:\n\t\t\tlines[r] = []\n\t\tlines[r].append([c1, c2])\n\ttot = 0\n\tfor x in lines:\n\t\tintervals = get_intervals(lines[x])\n\t\tsubtot = m\n\t\tfor x in intervals:\n\t\t\tsubtot -= x[1] - x[0] + 1\n\t\ttot += subtot\n\ttot += (n - len(lines)) * m\n\tprint(tot)\ntest()\n", "(n, m, k) = (int(x) for x in input().split())\n\ndef intersect(ab, xy):\n\tif ab[0] <= xy[0] and ab[1] >= xy[0]:\n\t\treturn True\n\tif ab[0] <= xy[1] and ab[1] >= xy[1]:\n\t\treturn True\n\treturn False\n\ndef superinterval(ab, xy):\n\treturn (min(ab[0], xy[0]), max(ab[1], xy[1]))\ntracks = dict()\nfor i in range(k):\n\t(r, c1, c2) = (int(x) for x in input().split())\n\tt = (c1, c2)\n\tdeletion = []\n\tif r not in tracks:\n\t\ttracks[r] = [t]\n\t\tcontinue\n\tfor (i, interval) in enumerate(tracks[r]):\n\t\tif intersect(interval, t):\n\t\t\tt = superinterval(interval, t)\n\t\t\tdeletion.append(i)\n\tfor i in reversed(deletion):\n\t\tdel tracks[r][i]\n\ttracks[r].append(t)\ncovered = 0\nfor row in tracks:\n\tfor track in tracks[row]:\n\t\tcovered += track[1] - track[0] + 1\nprint(n * m - covered)\n", "(n, m, k) = [int(x) for x in input().strip().split()]\ntrains = {}\nfor i in range(k):\n\t(r, c1, c2) = [int(x) for x in input().strip().split()]\n\tif r - 1 not in trains:\n\t\ttrains[r - 1] = []\n\ttrains[r - 1].append((c1 - 1, c2 - 1))\n\ndef combine_row(row):\n\tcur = row[0]\n\tresult = []\n\tfor (c1, c2) in row[1:]:\n\t\tif cur[0] <= c1 <= cur[1]:\n\t\t\tcur = (cur[0], max(cur[1], c2))\n\t\telse:\n\t\t\tresult.append(cur)\n\t\t\tcur = (c1, c2)\n\tresult.append(cur)\n\treturn result\nlamps = 0\nfor r in trains:\n\tls = 0\n\tfor (c1, c2) in combine_row(sorted(trains[r])):\n\t\tls += c2 - c1 + 1\n\tlamps += m - ls\nlamps += (n - len(trains)) * m\nprint(lamps)\n", "(n, m, k) = list(map(int, input().split(' ')))\ntotal = m * n\nrect = {}\nfor _q in range(k):\n\t(r, c1, c2) = list(map(int, input().split(' ')))\n\tif r in rect:\n\t\trect[r].append((c1, c2))\n\telse:\n\t\trect[r] = [(c1, c2)]\nsubt = 0\nfor (_key, liste) in rect.items():\n\tsorted_list = sorted(liste)\n\tlast_tup_end = 0\n\tfor tup in sorted_list:\n\t\tstart = tup[0]\n\t\tend = tup[1]\n\t\tif start <= last_tup_end:\n\t\t\tstart = last_tup_end + 1\n\t\tsubt += max(0, end - start + 1)\n\t\tlast_tup_end = max(last_tup_end, end)\nprint(total - subt)\n", "(n, m, k) = list(map(int, input().split()))\ncount = n * m\nd = dict()\nfor _ in range(k):\n\t(r, c1, c2) = list(map(int, input().split()))\n\tif not r in d:\n\t\td[r] = []\n\ttoRemove = []\n\tfor i in range(len(d[r])):\n\t\titem = d[r][i]\n\t\tif item[0] < c1:\n\t\t\tif item[1] < c1:\n\t\t\t\tcontinue\n\t\t\tc1 = item[0]\n\t\t\tif item[1] > c2:\n\t\t\t\tc2 = item[1]\n\t\t\ttoRemove.append(i)\n\t\telif item[0] == c1:\n\t\t\tif item[1] > c2:\n\t\t\t\tc2 = item[1]\n\t\t\ttoRemove.append(i)\n\t\telse:\n\t\t\tif item[1] > c2:\n\t\t\t\tcontinue\n\t\t\ttoRemove.append(i)\n\t\t\tif item[0] < c1:\n\t\t\t\tc1 = item[0]\n\tfor i in toRemove[::-1]:\n\t\tdel d[r][i]\n\td[r].append((c1, c2))\nfor item in d.values():\n\tfor j in item:\n\t\tcount -= j[1] - j[0] + 1\nprint(count)\n", "(n, m, k) = [int(item) for item in input().strip().split()]\nc = 0\noverlap = [0] * k\nrs = []\nop = 0\nfor i in range(k):\n\t(r, s, e) = [int(item) for item in input().strip().split()]\n\tc += e - s + 1\n\tif r not in rs:\n\t\trs.append(r)\n\t\toverlap[rs.index(r)] = [s, e]\n\telse:\n\t\tif e in range(overlap[rs.index(r)][0], overlap[rs.index(r)][1] + 1):\n\t\t\top += e - max(overlap[rs.index(r)][0], s) + 1\n\t\telif s in range(overlap[rs.index(r)][0], overlap[rs.index(r)][1] + 1):\n\t\t\top += min(overlap[rs.index(r)][1], e) - s + 1\n\t\t(overlap[rs.index(r)][0], overlap[rs.index(r)][1]) = (min(overlap[rs.index(r)][0], s), max(overlap[rs.index(r)][1], e))\nprint(n * m - c + op)\n", "s = 0\n(n, m, k) = [int(x) for x in input().split()]\nd = {}\nfor i in range(k):\n\t(r, c1, c2) = [int(x) for x in input().split()]\n\tif r not in d:\n\t\td[r] = list()\n\td[r].append((c1, c2))\nfor (k, v) in d.items():\n\ts1 = 0\n\tv = sorted(v)\n\tmn = 0\n\tmx = 0\n\tfor (c1, c2) in v:\n\t\tif mn == 0 and mx == 0:\n\t\t\ts1 += c2 - c1 + 1\n\t\t\tmn = c1\n\t\t\tmx = c2\n\t\telif c1 >= mn and c1 <= mx and (c2 >= mx):\n\t\t\ts1 += c2 - mx\n\t\t\tmx = c2\n\t\telif c1 > mx:\n\t\t\ts1 += c2 - c1 + 1\n\t\t\tmn = c1\n\t\t\tmx = c2\n\ts += s1\nprint(n * m - s)\n", "(n, m, k) = map(int, input().split())\nx = dict()\nval = n * m\nfor i in range(k):\n\t(r, c1, c2) = map(int, input().split())\n\tif r not in x:\n\t\tx[r] = (c1, c2)\n\telse:\n\t\tif x[r][1] < c1:\n\t\t\tval += c1 - x[r][1] - 1\n\t\telif x[r][0] > c2:\n\t\t\tval += x[r][0] - c2 - 1\n\t\tx[r] = (min(x[r][0], c1), max(x[r][1], c2))\nfor t in x.values():\n\tval -= t[1] - t[0] + 1\nprint(val)\n", "(rows, columns, tracks) = map(int, input().split())\ngrid = {}\nfor i in range(tracks):\n\taux = tuple(map(int, input().split()))\n\tif aux[0] in grid:\n\t\tgrid[aux[0]].append((aux[1], aux[2]))\n\telse:\n\t\tgrid[aux[0]] = [(aux[1], aux[2])]\nlamppost = (rows - len(grid)) * columns\nfor r in grid:\n\tauxR = grid[r]\n\tauxR = sorted(auxR)\n\tchanges = True\n\twhile changes:\n\t\tchanges = False\n\t\tfor i in range(1, len(auxR)):\n\t\t\tif auxR[i][0] <= auxR[i - 1][1]:\n\t\t\t\tchanges = True\n\t\t\t\tauxR = [(auxR[i - 1][0], max(auxR[i - 1][1], auxR[i][1]))] + auxR[i + 1:]\n\t\t\t\tbreak\n\tsumTracks = 0\n\tfor tr in auxR:\n\t\tsumTracks += tr[1] - tr[0] + 1\n\tlamppost += columns - sumTracks\nprint(lamppost)\n", "import sys\nx = sys.stdin.readlines()\n(N, M, K) = [int(i) for i in x[0].split(' ')]\nS = 0\nd = {}\nfor i in range(1, K + 1):\n\t(r, c1, c2) = [int(j) for j in x[i].split(' ')]\n\tif r not in d:\n\t\td[r] = []\n\td[r].append((c1, c2))\n\ndef qsort(L):\n\tif L:\n\t\treturn 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]])\n\treturn []\n\ndef lamps_in_row(r):\n\tA = []\n\tB = []\n\tfor i in r:\n\t\t(a, b) = i\n\t\tA.append(a)\n\t\tB.append(b)\n\tA = qsort(A)\n\tB = qsort(B)\n\tC = qsort(A + B)\n\ta_i = 0\n\tb_i = 0\n\ts = 0\n\tfor i in range(len(C)):\n\t\tcount = a_i - b_i\n\t\tif i > 0 and count == 0:\n\t\t\ts = C[i] - C[i - 1] - 1\n\t\tif a_i < len(A) and C[i] == A[a_i]:\n\t\t\ta_i = a_i + 1\n\t\telif b_i < len(B) and C[i] == B[b_i]:\n\t\t\tb_i = b_i + 1\n\treturn (s, A[0], B[-1])\nfor i in d:\n\t(s, a, b) = lamps_in_row(d[i])\n\tS = S + (b - a + 1 - s)\nprint(M * N - S)\n", "prams = list(map(int, input().split()))\ndic = {}\ns = 0\nfor a in range(prams[2]):\n\t[r, c1, c2] = list(map(int, input().split()))\n\tif r not in dic:\n\t\tdic[r] = [(c1, c2)]\n\t\ts += c2 - c1 + 1\n\telse:\n\t\ti = 0\n\t\tfor [k1, k2] in dic[r]:\n\t\t\tif c1 <= k1 and c2 >= k1 or (c2 >= k2 and c1 <= k2) or (c1 >= k1 and c2 <= k2):\n\t\t\t\tdic[r].pop(i)\n\t\t\t\ts -= k2 - k1 + 1\n\t\t\t\tc1 = min(c1, k1)\n\t\t\t\tc2 = max(c2, k2)\n\t\t\t\ts += c2 - c1 + 1\n\t\t\t\tdic[r].append((c1, c2))\n\t\t\t\tbreak\n\t\t\ti += 1\n\t\telse:\n\t\t\ts += c2 - c1 + 1\n\t\t\tdic[r].append((c1, c2))\ns = prams[0] * prams[1] - s\ns = max(s, 0)\nprint(s)\n", "[m, n, numTracks] = [int(i) for i in input().strip().split(' ')]\nrows = {}\n\nclass Point:\n\n\tdef __init__(self, tup):\n\t\tself.tup = tup\n\n\tdef __eq__(self, other):\n\t\tif isinstance(other, A):\n\t\t\treturn self.tup == other.tup\n\t\treturn NotImplemented\n\n\tdef __ne__(self, other):\n\t\tresult = self.__eq__(other)\n\t\tif result is NotImplemented:\n\t\t\treturn result\n\t\treturn not result\n\n\tdef __lt__(self, other):\n\t\treturn self.tup[1] - other.tup[1] < 0 or (self.tup[1] == other.tup[1] and self.tup[0] == 1)\n\n\tdef __gt__(self, other):\n\t\treturn self.tup[1] - other.tup[1] > 0 or (self.tup[1] == other.tup[1] and self.tup[0] == 2)\n\n\tdef __le__(self, other):\n\t\treturn self.__eq__(other) or self.__lt__(other)\n\n\tdef __ge__(self, other):\n\t\treturn self.__eq__(other) or self.__gt__(other)\n\n\tdef __getitem__(self, index):\n\t\treturn self.tup[index]\n\n\tdef __repr__(self):\n\t\treturn str(self.tup)\n\n\tdef __str__(self):\n\t\treturn str(self.tup)\nfor i in range(numTracks):\n\ttokens = input().strip().split(' ')\n\tl = [Point((1, int(tokens[1]))), Point((2, int(tokens[2])))]\n\tif rows.get(tokens[0], None) is None:\n\t\trows[tokens[0]] = l\n\telse:\n\t\trows[tokens[0]] += l\ncovered = 0\nfor i in rows:\n\trows[i].sort()\n\ts = 0\n\tstart = 0\n\te = 0\n\tfor tup in rows[i]:\n\t\tif tup[0] is 1:\n\t\t\tif s is 0:\n\t\t\t\tstart = tup[1]\n\t\t\ts += 1\n\t\telse:\n\t\t\te += 1\n\t\tif s is e:\n\t\t\tcovered += tup[1] - start + 1\n\t\t\ts = 0\n\t\t\te = 0\n\t\t\tstart = 0\nprint(m * n - covered)\n", "import sys\nimport bisect\nfrom collections import namedtuple\n\nclass TrackTuple(namedtuple('_TrackTuple', ['c1', 'c2'])):\n\n\tdef __lt__(self, o):\n\t\treturn self.c1 < o.c1\n\n\tdef __len__(self):\n\t\treturn self.c2 - self.c1 + 1\n\n\tdef combine(self, o):\n\t\tc1 = self.c1 if self.c1 <= o.c1 else o.c1\n\t\tc2 = self.c2 if self.c2 >= o.c2 else o.c2\n\t\treturn TrackTuple(c1, c2)\n(rows, cols, k) = [int(i) for i in input().strip().split(' ')]\nn_tracks = 0\nrails = {}\nfor j in range(k):\n\t(r, c1, c2) = [int(i) for i in input().strip().split(' ')]\n\tif c1 > c2:\n\t\t(c1, c2) = (c2, c1)\n\ttrack = TrackTuple(c1, c2)\n\trow_track = rails.setdefault(r, [])\n\trow_track_len = len(row_track)\n\tif row_track_len == 0:\n\t\trow_track.append(track)\n\t\ttrack_len = len(track)\n\telse:\n\t\ti = bisect.bisect(row_track, track)\n\t\trm_list = []\n\t\tif i > 0:\n\t\t\tt = row_track[i - 1]\n\t\t\tif c1 <= t.c2:\n\t\t\t\ttrack = track.combine(t)\n\t\t\t\trm_list.append(t)\n\t\tif i < row_track_len:\n\t\t\tt = row_track[i + 1]\n\t\t\tif c2 >= t.c1:\n\t\t\t\ttrack_len -= t.c2 - c1 + 1\n\t\t\t\ttrack = track.combine(t)\n\t\t\t\trm_list.append(t)\n\t\told_len = sum((len(t) for t in row_track))\n\t\trow_track.insert(i, track)\n\t\tfor t in rm_list:\n\t\t\trow_track.remove(t)\n\t\tnew_len = sum((len(t) for t in row_track))\n\t\ttrack_len = new_len - old_len\n\tn_tracks += track_len\nprint(rows * cols - n_tracks)\n", "import sys\n(n, m, k) = input().strip().split(' ')\nn = int(n)\nm = int(m)\ntraindict = {}\ncount = n * m\nfor i in range(int(k)):\n\t(row, c1, c2) = input().strip().split(' ')\n\trow = int(row)\n\tc1 = int(c1)\n\tc2 = int(c2)\n\tif row in traindict:\n\t\tif c1 < traindict[row][0]:\n\t\t\tif c2 < traindict[row][0]:\n\t\t\t\tcount = count - (c2 - c1 + 1)\n\t\t\t\ttraindict[row][0] = c1\n\t\t\telse:\n\t\t\t\tcount = count - (traindict[row][0] - c1)\n\t\t\t\ttraindict[row][0] = c1\n\t\tif c2 > traindict[row][1]:\n\t\t\tif c1 > traindict[row][1]:\n\t\t\t\tcount = count - (c2 - c1 + 1)\n\t\t\t\ttraindict[row][1] = c2\n\t\t\telse:\n\t\t\t\tcount = count - (c2 - traindict[row][1])\n\t\t\t\ttraindict[row][1] = c2\n\telse:\n\t\ttraindict[row] = [c1, c2]\n\t\tcount = count - (c2 - c1 + 1)\nprint(count)\n", "from collections import defaultdict\n(n, m, k) = [int(i) for i in input().strip().split(' ')]\nd = defaultdict(lambda : list())\nfor test in range(k):\n\t(r, c1, c2) = [int(i) for i in input().strip().split(' ')]\n\td[r].append([c1, c2])\ntotal = 0\nfor (keys, values) in d.items():\n\tv = sorted(values, key=lambda x: x[0])\n\tstart = v[0][0]\n\tend = v[0][1]\n\tfor i in range(1, len(v)):\n\t\tdata = v[i]\n\t\tif data[0] <= end:\n\t\t\tend = max(end, data[1])\n\t\telse:\n\t\t\ttotal += end - start + 1\n\t\t\tstart = data[0]\n\t\t\tend = data[1]\n\ttotal += end - start + 1\nprint(n * m - total)\n", "(N, M, k) = [int(n) for n in input().split()]\ntotal = 0\ntrains = []\nfor _ in range(k):\n\ttrains.append([int(n) for n in input().split()])\ntrains.sort(key=lambda x: x[0])\ntotal = 0\nprevRow = 1\nocc = 0\nprevEnd = 0\nfor train in trains:\n\tif train[0] > prevRow:\n\t\ttotal += (train[0] - prevRow) * M - occ\n\t\tocc = 0\n\t\tprevEnd = 0\n\t\tprevRow = train[0]\n\tif train[2] > prevEnd:\n\t\tif train[1] > prevEnd:\n\t\t\tocc += train[2] - train[1] + 1\n\t\telse:\n\t\t\tocc += train[2] - prevEnd\n\t\tprevEnd = max(prevEnd, train[2])\ntotal += (N + 1 - prevRow) * M - occ\nprint(total)\n", "from collections import defaultdict\n(n, m, k) = map(int, input().split())\nl = []\nfor _ in range(k):\n\tl.append([int(x) for x in input().strip().split()])\nd = defaultdict(list)\nfor x in l:\n\td[x[0]].append((x[1], x[2]))\nnew_l = []\nfor x in d.keys():\n\tnew_l.append(sorted(d[x], key=lambda x: (x[0], x[1])))\ntot = 0\nfor x in new_l:\n\t(temp1, temp2) = x[0]\n\tfor (c1, c2) in x:\n\t\tif c1 in range(temp1, temp2 + 1) and c2 in range(temp1, temp2 + 1):\n\t\t\tcontinue\n\t\tif c1 in range(temp1, temp2 + 1):\n\t\t\t(temp1, temp2) = (temp1, c2)\n\t\telse:\n\t\t\ttot += temp2 - temp1 + 1\n\t\t\t(temp1, temp2) = (c1, c2)\n\ttot += temp2 - temp1 + 1\nprint(n * m - tot)\n", "line1 = input().strip().split(' ')\nn = int(line1[0])\nm = int(line1[1])\nk = int(line1[2])\ntrackDict = {}\nfor x in range(k):\n\ttrack = list(map(int, input().strip().split(' ')))\n\tendPoints = track[1:]\n\tif track[0] in trackDict:\n\t\trowList = trackDict[track[0]]\n\t\ti = 0\n\t\twhile i < len(rowList) and rowList[i][0] < endPoints[0]:\n\t\t\ti = i + 1\n\t\trowList.insert(i, endPoints)\n\telse:\n\t\ttrackDict[track[0]] = [track[1:]]\ntotalOccupiedSquares = 0\nfor row in trackDict:\n\trowList = trackDict[row]\n\taIndex = 0\n\tbIndex = 1\n\twhile bIndex < len(rowList):\n\t\ta = rowList[aIndex]\n\t\tb = rowList[bIndex]\n\t\tif b[0] <= a[1]:\n\t\t\trowList[aIndex] = [a[0], max(a[1], b[1])]\n\t\t\tdel rowList[bIndex]\n\t\telse:\n\t\t\taIndex += 1\n\t\t\tbIndex += 1\n\tfor item in rowList:\n\t\ttotalOccupiedSquares += item[1] - item[0] + 1\nprint(m * n - totalOccupiedSquares)\n", "import sys\nfrom collections import defaultdict, deque\nfrom itertools import islice, chain\nROW = 0\nC1 = 1\nC2 = 2\n\ndef main(text=None):\n\t(n, m, trains) = parse_input(text)\n\tnum_cells = n * m\n\tif len(trains) == 0:\n\t\treturn num_cells\n\ttrains = merge_trains(trains)\n\toccupied = count_occupied(trains)\n\treturn num_cells - occupied\n\ndef parse_input(text=None):\n\tif not text:\n\t\ttext = sys.stdin.read().rstrip()\n\tlines = [list(map(int, l.rstrip().split(' '))) for l in text.split('\\n')]\n\t(n, m, k) = lines[0]\n\ttrains = lines[1:]\n\treturn (n, m, trains)\n\ndef merge_trains(all_trains):\n\ttrains_by_row = defaultdict(list)\n\tfor train in all_trains:\n\t\trow = train[ROW]\n\t\ttrains_by_row[row].append(train)\n\tnew_trains_by_row = defaultdict(list)\n\tfor (row, trains) in trains_by_row.items():\n\t\tif len(trains) == 1:\n\t\t\tnew_trains_by_row[row].append(trains[0])\n\t\t\tcontinue\n\t\ttrains = sorted(trains, key=lambda x: x[1:])\n\t\tlast_two = deque(trains[0:1], maxlen=2)\n\t\tfor t in islice(trains, 1, None):\n\t\t\tlast_two.append(t)\n\t\t\tif last_two[0][C2] + 1 >= last_two[1][C1]:\n\t\t\t\tmerged_train = [row, last_two[0][C1], max(last_two[0][C2], last_two[1][C2])]\n\t\t\t\tlast_two[1] = merged_train\n\t\t\telse:\n\t\t\t\tnew_trains_by_row[row].append(last_two[0])\n\t\tnew_trains_by_row[row].append(last_two[1])\n\treturn list(chain.from_iterable(new_trains_by_row.values()))\n\ndef count_occupied(trains):\n\treturn sum((t[C2] - t[C1] + 1 for t in trains))\nprint(main())\n", "import itertools\nfrom collections import deque\n\ndef calculate_lenghts(intervals):\n\tcurrent_interval = intervals.popleft()\n\tcombined_length = 0\n\twhile intervals:\n\t\tnext_interval = intervals.popleft()\n\t\tif current_interval[1] + 1 < next_interval[0]:\n\t\t\tcombined_length += current_interval[1] - current_interval[0] + 1\n\t\t\tcurrent_interval = next_interval\n\t\telse:\n\t\t\tcurrent_interval = (current_interval[0], max(current_interval[1], next_interval[1]))\n\tcombined_length += current_interval[1] - current_interval[0] + 1\n\treturn combined_length\n(row_count, col_count, n) = [int(x) for x in input().split()]\ngrid = []\nfor _ in range(n):\n\tgrid.append([int(x) for x in input().split()])\ngrid.sort()\ngrid_by_row = {}\nfor (k, g) in itertools.groupby(grid, lambda x: x[0]):\n\tgrid_by_row[k] = deque()\n\tfor (r, c1, c2) in g:\n\t\tgrid_by_row[k].append((c1, c2))\nresult = 0\nfor row in grid_by_row:\n\tlengths = calculate_lenghts(grid_by_row[row])\n\tresult += col_count - lengths\nresult += col_count * (row_count - len(grid_by_row))\nprint(result)\n", "(rows, cols, numTracks) = [int(x) for x in input().strip().split()]\ntracks = dict()\nfor _ in range(numTracks):\n\t(r, c1, c2) = [int(x) for x in input().strip().split()]\n\tif r not in tracks:\n\t\ttracks[r] = [[c1, c2]]\n\telse:\n\t\tfound = False\n\t\tfoundTrack = None\n\t\tfor track in tracks[r]:\n\t\t\tif c1 >= track[0] and c2 <= track[1]:\n\t\t\t\tfound = True\n\t\t\t\tfoundTrack = track\n\t\t\t\tbreak\n\t\t\telif c1 <= track[0] and c2 >= track[1]:\n\t\t\t\ttrack[0] = c1\n\t\t\t\ttrack[1] = c2\n\t\t\t\tfound = True\n\t\t\t\tfoundTrack = track\n\t\t\t\tbreak\n\t\t\telif c1 < track[0] and track[0] <= c2 <= track[1]:\n\t\t\t\ttrack[0] = c1\n\t\t\t\tfound = True\n\t\t\t\tfoundTrack = track\n\t\t\t\tbreak\n\t\t\telif c2 > track[1] and track[0] <= c1 <= track[1]:\n\t\t\t\ttrack[1] = c2\n\t\t\t\tfound = True\n\t\t\t\tfoundTrack = track\n\t\t\t\tbreak\n\t\tif not found:\n\t\t\ttracks[r].append([c1, c2])\n\t\telse:\n\t\t\tfor track in tracks[r].copy():\n\t\t\t\tif track == foundTrack:\n\t\t\t\t\tcontinue\n\t\t\t\telif track[0] <= foundTrack[1]:\n\t\t\t\t\ttrack[0] = foundTrack[1] + 1\n\t\t\t\telif track[1] >= foundTrack[0]:\n\t\t\t\t\ttrack[1] = foundTrack[0] - 1\n\t\t\t\tif track[1] < track[0]:\n\t\t\t\t\ttracks[r].remove(track)\ntrackSquares = 0\nfor v in tracks.values():\n\tfor track in v:\n\t\ttrackSquares += track[1] - track[0] + 1\nprint(rows * cols - trackSquares)\n", "def main():\n\t(n, m, k) = [int(temp) for temp in input().strip().split(' ')]\n\tt = n * m\n\tx = {}\n\tc = 0\n\tfor i in range(k):\n\t\t(r, c1, c2) = [int(temp) for temp in input().strip().split(' ')]\n\t\tif r in x.keys():\n\t\t\t(xc1, xc2) = (x[r][0], x[r][1])\n\t\t\tif not (c2 < xc1 or c1 > xc2):\n\t\t\t\tif c1 <= xc1 and c2 >= xc2:\n\t\t\t\t\tc -= xc2 - xc1 + 1\n\t\t\t\t\tx[r] = [c1, c2]\n\t\t\t\telif c1 > xc1 and c2 >= xc2:\n\t\t\t\t\tc -= xc2 - c1 + 1\n\t\t\t\t\tx[r][1] = c2\n\t\t\t\telif c1 <= xc1 and c2 < xc2:\n\t\t\t\t\tc -= c2 - xc1 + 1\n\t\t\t\t\tx[r][0] = c1\n\t\t\t\telse:\n\t\t\t\t\tcontinue\n\t\telse:\n\t\t\tx[r] = [c1, c2]\n\t\tc += c2 - c1 + 1\n\tprint(t - c)\nmain()\n", "(m, n, k) = map(int, input().split())\nlamp = 0\nb = {}\nfor i in range(k):\n\t(r, c1, c2) = map(int, input().split())\n\tif r not in b:\n\t\tb[r] = [[c1, c2]]\n\telse:\n\t\tb[r].append([c1, c2])\nfor i in b.keys():\n\tb[i].sort(key=lambda l: l[0])\n\tflag = 1\n\twhile flag:\n\t\tflag = 0\n\t\tfor j in range(len(b[i]) - 1):\n\t\t\tif b[i][j][1] >= b[i][j + 1][0]:\n\t\t\t\tflag = 1\n\t\t\t\tif b[i][j][1] < b[i][j + 1][1]:\n\t\t\t\t\tb[i][j][1] = b[i][j + 1][1]\n\t\t\t\tb[i].pop(j + 1)\n\t\t\t\tbreak\nfor i in b.keys():\n\ttemp = 0\n\tfor j in range(len(b[i])):\n\t\ttemp += b[i][j][1] - b[i][j][0] + 1\n\tlamp += n - temp\nlamp += (m - len(b.keys())) * n\nprint(lamp)\n", "(N, M, K) = tuple(map(int, input().split()))\nr_situation = {}\nfor _ in range(K):\n\t(r, begin, end) = tuple(map(int, input().split()))\n\tif not r_situation.get(r):\n\t\tr_situation[r] = []\n\tr_situation[r].append((begin, end))\ntrack_spaces = 0\nfor R in r_situation.values():\n\tR.sort()\n\ttrack_spaces += R[0][1] - R[0][0] + 1\n\tfor idx in range(1, len(R)):\n\t\ttrack_pair = R[idx]\n\t\tlongest_track_end = -1\n\t\tfor log_idx in range(idx - 1, -1, -1):\n\t\t\tlog_track_pair = R[log_idx]\n\t\t\tif track_pair[0] <= log_track_pair[1]:\n\t\t\t\tlongest_track_end = max(longest_track_end, log_track_pair[1])\n\t\tif longest_track_end == -1:\n\t\t\ttrack_spaces += track_pair[1] - track_pair[0] + 1\n\t\telif longest_track_end <= track_pair[1]:\n\t\t\ttrack_spaces += track_pair[1] - longest_track_end\nprint(N * M - track_spaces)\n", "def Overlap_interval(inp):\n\tres = []\n\tif len(inp) == 1:\n\t\treturn inp\n\tlength = len(inp)\n\ti = 0\n\tj = 0\n\twhile i < length:\n\t\tstart = inp[i][0]\n\t\tend = inp[i][1]\n\t\twhile j < length and (start <= inp[j][0] and inp[j][1] <= end or (start <= inp[j][0] and inp[j][0] <= end)):\n\t\t\tend = max(end, inp[j][1])\n\t\t\tj += 1\n\t\ti = j\n\t\tj += 1\n\t\tres.append((start, end))\n\treturn res\n(n, m, k) = map(int, input().strip().split())\nname_map = {}\nnum = 0\ninp = []\nfor i in range(k):\n\t(r, c1, c2) = map(int, input().strip().split())\n\tif r in name_map.keys():\n\t\tindex = name_map[r]\n\t\tinp[index].append((c1, c2))\n\telse:\n\t\tname_map[r] = num\n\t\tindex = num\n\t\tinp.append([])\n\t\tinp[-1].append((c1, c2))\n\t\tnum += 1\nresult = n * m\nfor i in range(len(inp)):\n\tinp[i].sort()\n\tinp[i] = Overlap_interval(inp[i])\n\tfor j in inp[i]:\n\t\tvalue = j[1] - j[0] + 1\n\t\tresult -= value\nprint(result)\n", "def mergeTwoTracks(t1, t2):\n\tstart = 0\n\tend = 0\n\tif t1[1] <= t2[1]:\n\t\tstart = t1[1]\n\telse:\n\t\tstart = t2[1]\n\tif t1[2] >= t2[2]:\n\t\tend = t1[2]\n\telse:\n\t\tend = t2[2]\n\treturn [t1[0], start, end]\n\ndef checkIntersection(t1, t2):\n\tif t1[0] != t2[0]:\n\t\treturn False\n\tif t1[1] >= t2[1] and t1[1] <= t2[2]:\n\t\treturn True\n\tif t1[2] <= t2[2] and t1[2] >= t2[1]:\n\t\treturn True\n\tif t2[1] >= t1[1] and t2[1] <= t1[2]:\n\t\treturn True\n\tif t2[2] <= t1[2] and t2[2] >= t1[1]:\n\t\treturn True\n\treturn False\n\ndef checkForMerge(tracks):\n\tfor i in range(len(tracks) - 1):\n\t\tcurr = tracks[i]\n\t\tfor j in range(i + 1, len(tracks)):\n\t\t\tif checkIntersection(curr, tracks[j]):\n\t\t\t\ttracks[i] = mergeTwoTracks(curr, tracks[j])\n\t\t\t\ttracks.remove(tracks[j])\n\t\t\t\treturn [tracks, True]\n\treturn [tracks, False]\nline = list(map(int, input().split(' ')))\ntracks = []\nfor i in range(line[2]):\n\ttracks.append(list(map(int, input().split(' '))))\ncheck = True\nwhile check:\n\tresult = checkForMerge(tracks)\n\ttracks = result[0]\n\tcheck = result[1]\ntaken = 0\nfor i in range(len(tracks)):\n\ttaken += tracks[i][2] - tracks[i][1] + 1\ntaken = line[0] * line[1] - taken\nprint(taken)\n", "def within(num, tup):\n\treturn num >= tup[0] and num <= tup[1]\n(n, m, k) = (int(i) for i in input().split())\ntracks = {}\nnum = 0\nfor _ in range(k):\n\t(r, c1, c2) = (int(i) - 1 for i in input().split())\n\tif r not in tracks:\n\t\ttracks[r] = []\n\ttracks[r].append((c1, c2))\nfor r in tracks:\n\tif len(tracks[r]) == 1:\n\t\tnum += tracks[r][0][1] - tracks[r][0][0] + 1\n\telse:\n\t\tfinal = []\n\t\trow = sorted(tracks[r], key=lambda x: x[0])\n\t\tfor i in range(len(row) - 1):\n\t\t\tif within(row[i + 1][0], row[i]):\n\t\t\t\tif within(row[i + 1][1], row[i]):\n\t\t\t\t\tfinal.append(row[i])\n\t\t\t\telse:\n\t\t\t\t\tfinal.append((row[i][0], row[i + 1][1]))\n\t\t\t\trow[i + 1] = final[-1]\n\t\t\telse:\n\t\t\t\tfinal.append(row[i])\n\t\trepeats = [track[0] for track in row]\n\t\tfor (i, elem) in enumerate(repeats):\n\t\t\tif elem in repeats[i + 1:]:\n\t\t\t\trow[i] = False\n\t\tfor track in row:\n\t\t\tif track:\n\t\t\t\tnum += track[1] - track[0] + 1\nprint(n * m - num)\n", "def row_calc(array):\n\tn = len(array)\n\tarray = sorted(array)\n\tnew_array = []\n\tanswer = 0\n\tprev_1 = array[0][1]\n\tprev_2 = array[0][2]\n\tfor x in range(n - 1):\n\t\tif prev_2 >= array[x + 1][1]:\n\t\t\tif prev_2 >= array[x + 1][2]:\n\t\t\t\tarray[x + 1][1] = prev_2\n\t\t\t\tarray[x + 1][2] = prev_2 - 1\n\t\t\telse:\n\t\t\t\tarray[x + 1][1] = prev_2 + 1\n\t\t\t\tprev_1 = array[x + 1][1]\n\t\t\t\tprev_2 = array[x + 1][2]\n\t\telse:\n\t\t\tprev_1 = array[x + 1][1]\n\t\t\tprev_2 = array[x + 1][2]\n\tfor x in range(n):\n\t\tanswer += array[x][2] - array[x][1] + 1\n\treturn answer\n(n, m, k) = list((int(x) for x in input().split()))\ntracks = []\nfor x in range(k):\n\ttrack = list((int(x) for x in input().split()))\n\ttracks.append(track)\ntracks = sorted(tracks)\nanswer1 = 0\nx = 0\nwhile x < k:\n\ttrack_list = []\n\ttrack_list.append(tracks[x])\n\ttry:\n\t\twhile tracks[x][0] == tracks[x + 1][0]:\n\t\t\ttrack_list.append(tracks[x + 1])\n\t\t\tx += 1\n\texcept:\n\t\tpass\n\tanswer1 += row_calc(track_list)\n\tx += 1\nanswer = n * m - answer1\nprint(answer)\n", "(row_count, column_count, track_count) = map(int, input().strip().split(' '))\nrow_usage = dict()\nfor track in range(track_count):\n\t(row, start_column, stop_column) = map(int, input().strip().split(' '))\n\trow_sections = row_usage.get(row)\n\tif row_sections is None:\n\t\trow_usage[row] = [[start_column, stop_column]]\n\telse:\n\t\tnew_used = []\n\t\tfor section in row_sections:\n\t\t\tif section[1] < start_column or stop_column < section[0]:\n\t\t\t\tnew_used.append(section)\n\t\t\telse:\n\t\t\t\tstart_column = min(start_column, section[0])\n\t\t\t\tstop_column = max(stop_column, section[1])\n\t\tnew_used.append((start_column, stop_column))\n\t\trow_usage[row] = new_used\nfree_cells_count = row_count * column_count\nfor (row_number, row_sections) in row_usage.items():\n\tfor section in row_sections:\n\t\tfree_cells_count -= section[1] - section[0] + 1\nprint(free_cells_count)\n", "from operator import itemgetter\n\ndef fun(temp, m):\n\tn = len(temp)\n\ttemp.sort(key=itemgetter(0))\n\tans = [[temp[0][0], temp[0][1]]]\n\tfor i in range(1, n):\n\t\tif temp[i][0] <= ans[-1][1]:\n\t\t\tif temp[i][1] > ans[-1][1]:\n\t\t\t\tans[-1] = [ans[-1][0], temp[i][1]]\n\t\telse:\n\t\t\tans.append([temp[i][0], temp[i][1]])\n\tres = 0\n\tfor i in ans:\n\t\tres += i[1] - i[0] + 1\n\treturn m - res\n(n, m, k) = [int(i) for i in input().split()]\na = [[0, 0, 0] for i in range(k)]\nfor i in range(k):\n\ta[i] = [int(j) for j in input().split()]\na.sort(key=itemgetter(0))\nans = 0\nind = 0\n(start, end) = (0, 0)\nc = 0\nwhile ind < k:\n\ttemp = []\n\tstart = a[ind][1]\n\tend = a[ind][2]\n\ttemp.append([start, end])\n\tind += 1\n\tc += 1\n\twhile ind < k and a[ind][0] == a[ind - 1][0]:\n\t\tstart = a[ind][1]\n\t\tend = a[ind][2]\n\t\tind += 1\n\t\ttemp.append([start, end])\n\tans += fun(temp, m)\nans += (n - c) * m\nprint(ans)\n", "(n, m, k) = [int(i) for i in input().split()]\nans = 0\nd = {}\nfor _ in range(k):\n\t(r, c1, c2) = [int(i) for i in input().split()]\n\tif r not in d:\n\t\td[r] = [c1, c2]\n\telif d[r][0] <= c1 <= d[r][1] or d[r][0] <= c2 <= d[r][1]:\n\t\tt1 = min(c1, d[r][0])\n\t\tt2 = max(c2, d[r][1])\n\t\td[r] = [t1, t2]\n\telse:\n\t\tif c1 > d[r][1]:\n\t\t\tans -= c1 - d[r][1] - 1\n\t\telse:\n\t\t\tans -= d[r][0] - c2 - 1\n\t\tt1 = min(c1, d[r][0])\n\t\tt2 = max(c2, d[r][1])\n\t\td[r] = [t1, t2]\nfor i in d:\n\tans += d[i][1] - d[i][0] + 1\nprint(n * m - ans)\n", "def main():\n\t(rowNum, colNum, trackNum) = map(int, input().strip().split(' '))\n\tintervalListDict = dict()\n\tfor trackIdx in range(trackNum):\n\t\t(r, c1, c2) = map(int, input().strip().split(' '))\n\t\tintervalListDict[r] = intervalListDict.get(r, [])\n\t\tintervalListDict[r].append((c1, c2))\n\tcoveredCells = 0\n\tfor intervalList in intervalListDict.values():\n\t\tcoveredCells += countCoveredCells(intervalList)\n\tprint(rowNum * colNum - coveredCells)\n\ndef countCoveredCells(intervalList):\n\tmerged = []\n\tfor i in sorted(intervalList, key=lambda i: i[0]):\n\t\tif merged and i[0] <= merged[-1][1]:\n\t\t\tmerged[-1] = (merged[-1][0], max(merged[-1][1], i[1]))\n\t\telse:\n\t\t\tmerged.append(i)\n\tcells = 0\n\tfor i in merged:\n\t\tcells += i[1] - i[0] + 1\n\treturn cells\nmain()\n", "import sys\nfrom collections import defaultdict\nlines = sys.stdin.read().rstrip().split('\\n')\n\ndef createTrainInfoDict(trainInfo):\n\trow_to_trains = defaultdict(list)\n\tfor train in trainInfo:\n\t\t(row, start, end) = [int(i) for i in train.split()]\n\t\trow_to_trains[row].append((start, end))\n\treturn row_to_trains\n\ndef countNonAvailableSpotsInRow(trains, r_num):\n\ttrains = sorted(trains, key=lambda train: train[0])\n\tnumUnavailableSpots = 0\n\tcurrentEndPoint = 0\n\tfor train in trains:\n\t\tif train[1] > currentEndPoint:\n\t\t\toffset = 0\n\t\t\tif train[0] <= currentEndPoint:\n\t\t\t\toffset = currentEndPoint - train[0] + 1\n\t\t\tlength = train[1] - train[0] + 1\n\t\t\tnumUnavailableSpots += length - offset\n\t\t\tcurrentEndPoint = train[1]\n\treturn numUnavailableSpots\n\ndef countNumberOfSpots(lines):\n\t(r_num, c_num, k_num) = [int(i) for i in lines[0].split()]\n\tif k_num == 0:\n\t\treturn r_num * c_num\n\trows_to_trains = createTrainInfoDict(lines[1:])\n\tavailable = r_num * c_num\n\tfor row_key in rows_to_trains:\n\t\tavailable -= countNonAvailableSpotsInRow(rows_to_trains[row_key], r_num)\n\treturn available\nprint(countNumberOfSpots(lines))\n", "(n, m, k) = [int(x) for x in input().split()]\ntrain = []\nfor i in range(0, k):\n\t(r, c1, c2) = [int(x) for x in input().split()]\n\ttrain.append((r, c1, c2))\ntrain.sort()\n(row, startT, endT) = (0, 0, 0)\n(total, rowtrain) = (0, 0)\nrch = False\nfor item in train:\n\tif item[0] != row:\n\t\trch = True\n\t\ttotal = total + (rowtrain + (endT - startT + 1))\n\t\t(row, startT, endT) = item\n\t\trowtrain = 0\n\telse:\n\t\trch = False\n\t\tif item[1] <= endT:\n\t\t\tif endT < item[2]:\n\t\t\t\tendT = item[2]\n\t\telse:\n\t\t\trowtrain = rowtrain + (endT - startT + 1)\n\t\t\tstartT = item[1]\n\t\t\tendT = item[2]\nif rch:\n\ttotal += endT - startT + 1\nelse:\n\ttotal += rowtrain + (endT - startT + 1)\ntotal = total - 1\nprint(m * n - total)\n", "(n, m, k) = map(int, input().split())\ntotal = n * m\nd = {}\nt = 0\nfor _ in range(k):\n\t(r, c1, c2) = map(int, input().split())\n\tif r not in d:\n\t\td[r] = []\n\t\td[r].append(c1)\n\t\td[r].append(c2)\n\telse:\n\t\tif c2 < d[r][0]:\n\t\t\tt += d[r][0] - c2 - 1\n\t\tif c1 > d[r][1]:\n\t\t\tt += c1 - d[r][1] - 1\n\t\tif c1 <= d[r][0] and c2 >= d[r][1]:\n\t\t\tt = 0\n\t\tif c1 < d[r][0]:\n\t\t\td[r][0] = c1\n\t\tif c2 > d[r][1]:\n\t\t\td[r][1] = c2\nfor k in d:\n\ttotal = total - (d[k][1] - d[k][0] + 1) + t\nprint(total)\n", "class Track:\n\n\tdef __init__(self, c1, c2):\n\t\tself.c1 = c1\n\t\tself.c2 = c2\n\n\tdef __lt__(self, d):\n\t\tif self.c1 == d.c1:\n\t\t\treturn self.c2 < d.c2\n\t\treturn self.c1 < d.c1\n(n, m, k) = [int(x) for x in input().split()]\nrows = {}\nfor _ in range(k):\n\t(r, c1, c2) = [int(x) for x in input().split()]\n\tif r not in rows:\n\t\trows[r] = []\n\trows[r].append(Track(c1, c2))\nresult = n * m\nfor (r, row) in rows.items():\n\trow.sort()\n\tr_n = len(row)\n\ttotal = 0\n\t(st, ed) = (row[0].c1, row[0].c2)\n\tfor i in range(1, r_n):\n\t\ttrack = row[i]\n\t\tif track.c1 <= ed:\n\t\t\ted = max(ed, track.c2)\n\t\telse:\n\t\t\ttotal -= ed - st + 1\n\t\t\t(st, ed) = (track.c1, track.c2)\n\ttotal -= ed - st + 1\n\tresult += total\nprint(result)\n", "import copy\n\ndef sortIt(x):\n\ti = 0\n\twhile i < len(x) - 2:\n\t\tj = i + 2\n\t\tmin = i\n\t\twhile j < len(x):\n\t\t\tif x[min] > x[j]:\n\t\t\t\tmin = j\n\t\t\tj += 2\n\t\tif min != i:\n\t\t\t(x[i], x[i + 1], x[min], x[min + 1]) = (x[min], x[min + 1], x[i], x[i + 1])\n\t\ti += 2\n(n, m, k) = (int(x) for x in input().split())\ntracks = {}\nwhile k > 0:\n\t(r, c1, c2) = (int(x) for x in input().split())\n\tif r not in tracks.keys():\n\t\ttracks[r] = [c1, c2]\n\telse:\n\t\ttracks[r].append(c1)\n\t\ttracks[r].append(c2)\n\tk -= 1\ncount = 0\nfor row in tracks.keys():\n\ttemp = copy.deepcopy(tracks[row])\n\tsortIt(temp)\n\tcount += temp[1] - temp[0] + 1\n\tstart = 2\n\tdaddy = temp[1]\n\twhile start < len(temp):\n\t\tif temp[start] > daddy:\n\t\t\tcount += temp[start + 1] - temp[start] + 1\n\t\t\tdaddy = temp[start + 1]\n\t\telif temp[start] <= daddy:\n\t\t\tif temp[start + 1] >= daddy:\n\t\t\t\tcount += temp[start + 1] - daddy\n\t\t\t\tdaddy = temp[start + 1]\n\t\tstart += 2\nprint(n * m - count)\n", "from collections import defaultdict\n\ndef merge_ranges(ranges):\n\tranges = iter(sorted(ranges))\n\t(current_start, current_stop) = next(ranges)\n\tfor (start, stop) in ranges:\n\t\tif start > current_stop:\n\t\t\tyield (current_start, current_stop)\n\t\t\t(current_start, current_stop) = (start, stop)\n\t\telse:\n\t\t\tcurrent_stop = max(current_stop, stop)\n\tyield (current_start, current_stop)\n\ndef main():\n\td = defaultdict(list)\n\t(n, m, k) = map(int, input().split())\n\tres = 0\n\tfor _ in range(k):\n\t\tline = [int(a) for a in input().split(' ')]\n\t\td[line[0]].append(line[1:])\n\tfor ranges in d.values():\n\t\tl = list(merge_ranges(ranges))\n\t\tres += sum((l[i][0] - l[i - 1][1] - 1 for i in range(1, len(l))))\n\t\tres += l[0][0] - 1 + (m - l[-1][1])\n\tres += (n - len(d)) * m\n\tprint(res)\nmain()\n", "import sys\nfrom collections import defaultdict\n\ndef count_cells(rset):\n\tranges = sorted(map(list, rset))\n\tmerged = [ranges[0]]\n\tfor r in ranges[1:]:\n\t\tif r[0] <= merged[-1][1]:\n\t\t\tmerged[-1][1] = max(merged[-1][1], r[1])\n\t\telse:\n\t\t\tmerged.append(r)\n\treturn sum((x[1] - x[0] + 1 for x in merged))\nit = map(int, sys.stdin.read().split())\n(n, m) = (next(it), next(it))\nnext(it)\ntracks = defaultdict(set)\nfor (r, c1, c2) in zip(it, it, it):\n\ttracks[r].add((c1, c2))\ncells_in_rows = (count_cells(ranges) for ranges in tracks.values())\nprint(m * n - sum(cells_in_rows))\n", "(n, m, k) = input().split(' ')\n(n, m, k) = [int(n), int(m), int(k)]\ntracks = []\nfor t1 in range(k):\n\ttracks.append([int(t) for t in input().split(' ')])\ntracks.sort()\nif k == 0:\n\tprint(n * m)\nelse:\n\tr = tracks[0][0]\n\tc1 = tracks[0][1]\n\tc2 = tracks[0][2]\n\tcount = (r - 1) * m\n\tprev_row = r\n\tnon_over_laps = 0\n\tfor i in range(1, k):\n\t\tif tracks[i][0] == prev_row:\n\t\t\tc3 = tracks[i][1]\n\t\t\tc4 = tracks[i][2]\n\t\t\tif c3 <= c2 and c4 > c2:\n\t\t\t\tc2 = c4\n\t\t\telif c3 > c2:\n\t\t\t\tnon_over_laps += c2 - c1 + 1\n\t\t\t\tc1 = c3\n\t\t\t\tc2 = c4\n\t\telse:\n\t\t\tcount += (tracks[i][0] - prev_row - 1) * m\n\t\t\tif non_over_laps > 0:\n\t\t\t\tcount += m - (c2 - c1 + 1) - non_over_laps\n\t\t\telse:\n\t\t\t\tcount += m - (c2 - c1 + 1)\n\t\t\tprev_row = tracks[i][0]\n\t\t\tc1 = tracks[i][1]\n\t\t\tc2 = tracks[i][2]\n\t\t\tnon_over_laps = 0\n\tif non_over_laps > 0:\n\t\tcount += m - (c2 - c1 + 1) - non_over_laps\n\telse:\n\t\tcount += m - (c2 - c1 + 1)\n\tif prev_row < n:\n\t\tcount += (n - prev_row) * m\n\tprint(count)\n", "import sys\nfrom operator import itemgetter, attrgetter, methodcaller\n\ndef create_grid(nr, mc):\n\treturn [[1 for i in range(nr)] for j in range(mc)]\n\ndef mark_track(grid, r, c1, c2):\n\tr0 = r - 1\n\tfor c in range(c1 - 1, c2):\n\t\tgrid[c][r0] = 0\n\ndef count_free(grid):\n\tres = 0\n\tfor col in grid:\n\t\tres += sum(col)\n\treturn res\n\nclass Track(object):\n\tr = None\n\tc1 = None\n\tc2 = None\n\n\tdef __init__(self, r_, c1_, c2_):\n\t\tself.r = r_\n\t\tself.c1 = min(c1_, c2_)\n\t\tself.c2 = max(c1_, c2_)\n\n\tdef getLength(self):\n\t\treturn self.c2 - self.c1 + 1\n\n\tdef _sortKey(self):\n\t\treturn (self.r, self.c1, 1.0 / self.getLength())\n\n\tdef __cmp__(self, other):\n\t\treturn self._sortKey().__cmp__(other._sortKey())\n\n\tdef __cmp__(self, other):\n\t\treturn self._sortKey().__cmp__(other._sortKey())\n\n\tdef getR(self):\n\t\treturn self.r\n\n\tdef getC1(self):\n\t\treturn self.c1\n\n\tdef getC2(self):\n\t\treturn self.c2\n\n\tdef doesOverlap(self, other):\n\t\tif self._sortKey() <= other._sortKey():\n\t\t\t(t1, t2) = (self, other)\n\t\telse:\n\t\t\t(t1, t2) = (other, self)\n\t\treturn (t1.getR() == t2.getR()) & (t1.getC2() >= t2.getC1())\n\n\tdef createContaining(self, other):\n\t\treturn Track(self.r, min(self.getC1(), other.getC1()), max(self.getC2(), other.getC2()))\n\ndef sumUsed(tracks):\n\tsum = 0\n\tfor track in tracks:\n\t\tsum += track.getLength()\n\treturn sum\n\ndef do_it():\n\t(n, m, k) = [int(c_temp) for c_temp in input().strip().split(' ')]\n\ttracks = []\n\tfor trackIdx in range(k):\n\t\t(r, c1, c2) = [int(c_temp) for c_temp in input().strip().split(' ')]\n\t\ttracks.append(Track(r, c1, c2))\n\ttracks = sorted(tracks, key=methodcaller('_sortKey'))\n\tif len(tracks) > 0:\n\t\ttlast = tracks[0]\n\t\ttail = tracks[1:]\n\t\ttracks = []\n\t\tfor tnext in tail:\n\t\t\tif tlast.doesOverlap(tnext):\n\t\t\t\ttlast = tlast.createContaining(tnext)\n\t\t\telse:\n\t\t\t\ttracks.append(tlast)\n\t\t\t\ttlast = tnext\n\t\ttracks.append(tlast)\n\tprint('%d' % (n * m - sumUsed(tracks)))\ndo_it()\n", "from collections import defaultdict\n\ndef count_elements(ranges):\n\tranges.sort()\n\tresult_ranges = []\n\twhile ranges:\n\t\tfirst = ranges.pop(0)\n\t\twhile ranges:\n\t\t\tn = ranges[0]\n\t\t\tif first[0] <= n[0] <= first[1] or first[0] <= n[1] <= first[1]:\n\t\t\t\tfirst = (min(first[0], n[0]), max(first[1], n[1]))\n\t\t\t\tranges.pop(0)\n\t\t\telse:\n\t\t\t\tbreak\n\t\tresult_ranges.append(first)\n\treturn sum((e - s + 1 for (s, e) in result_ranges))\nd = defaultdict(list)\n(n, m, k) = map(int, input().split())\nfor _ in range(k):\n\t(r, s, e) = map(int, input().split())\n\td[r].append((s, e))\nd = {r: count_elements(ranges) for (r, ranges) in d.items()}\nprint(n * m - sum(d.values()))\n", "(a, b, c) = input().strip().split(' ')\n(a, b, c) = [int(a), int(b), int(c)]\nd = {}\nw = {}\nfor i in range(c):\n\t(r, c1, c2) = input().strip().split(' ')\n\t(r, c1, c2) = [int(r), int(c1), int(c2)]\n\tif r in d:\n\t\tf = d[r]\n\t\tif c2 < f[0] - 1:\n\t\t\tw[r] = f[0] - 1 - c2\n\t\tif c1 > f[1] + 1:\n\t\t\tw[r] = c1 - f[1] - 1\n\t\tf[0] = min(f[0], c1)\n\t\tf[1] = max(f[1], c2)\n\t\td[r] = f\n\telse:\n\t\td[r] = [c1, c2]\n\t\tw[r] = 0\nm = 0\nfor k in d:\n\tm += d[k][1] - d[k][0] + 1 - w[k]\nx = a * b - m\nprint(x)\n", "(n, m, k) = [int(x) for x in input().split()]\ntotal = n * m\ntracks = {}\nfor _ in range(k):\n\t(r, start, end) = [int(x) for x in input().split()]\n\ttracks.setdefault(r, []).append((start, end))\noccupied = 0\nfor (key, values) in tracks.items():\n\tvalues.sort(key=lambda x: x[0])\n\tlast = -1\n\tfor (start, end) in values:\n\t\tif start <= last:\n\t\t\tstart = last + 1\n\t\tsl = end - start + 1\n\t\tif sl > 0:\n\t\t\toccupied += sl\n\t\t\tlast = end\nprint(total - occupied)\n", "def count_lamposts(n, m, tracks):\n\ttracks.sort()\n\tcount = 0\n\t(r, c1, c2) = (0, 0, 0)\n\tfor (ri, ci, cj) in tracks:\n\t\tif ri != r:\n\t\t\tcount += m - c2 if r > 0 else 0\n\t\t\tcount += (ri - (r + 1)) * m\n\t\t\t(r, c1, c2) = (ri, 0, 0)\n\t\tif ci > c2:\n\t\t\tcount += ci - (c2 + 1)\n\t\t\tc1 = ci\n\t\tif cj > c2:\n\t\t\tc2 = cj\n\tcount += m - c2 if r > 0 else 0\n\tcount += (n - r) * m\n\treturn count\n(n, m, k) = [int(n) for n in input().split()]\ntracks = [[int(n) for n in input().split()] for _ in range(k)]\nprint(count_lamposts(n, m, tracks))\n", "(m, n, k) = [int(i) for i in input().strip().split(' ')]\ntracks = {}\nfor _ in range(k):\n\t(r, c1, c2) = [int(i) for i in input().strip().split(' ')]\n\tif r not in tracks.keys():\n\t\ttracks[r] = [[c1, c2]]\n\telse:\n\t\tfor j in tracks[r]:\n\t\t\tmerged = False\n\t\t\tif c1 >= j[0] and c1 <= j[1]:\n\t\t\t\tj[1] = max(j[1], c2)\n\t\t\t\tmerged = True\n\t\t\tif c2 >= j[0] and c2 <= j[1]:\n\t\t\t\tj[0] = min(j[0], c1)\n\t\t\t\tmerged = True\n\t\t\tif not merged:\n\t\t\t\ttracks[r].append([c1, c2])\n\t\t\tbreak\nres = n * m\nfor i in tracks.keys():\n\tfor j in tracks[i]:\n\t\tres -= j[1] - j[0] + 1\nprint(res)\n", "import sys\n(n, m, k) = [int(i) for i in input().split()]\nrows = {}\nnon = 0\nfor i in range(k):\n\t(row_k, c1, c2) = input().split()\n\tc1 = int(c1)\n\tc2 = int(c2)\n\tif row_k in rows.keys():\n\t\tif c1 - rows[row_k][1] > 1:\n\t\t\tnon += c1 - rows[row_k][1] - 1\n\t\trows[row_k][0] = min(c1, rows[row_k][0])\n\t\trows[row_k][1] = max(c2, rows[row_k][1])\n\telse:\n\t\trows[row_k] = [c1, c2]\ntotal_cells = n * m\noccupied_cells = sum([1 + i[1] - i[0] for i in rows.values()])\nprint(total_cells - occupied_cells + non)\n", "(n, m, k) = map(int, input().split())\ntrains = {}\nfor i in range(k):\n\t(r, left, right) = map(int, input().split())\n\tif r in trains:\n\t\ttrains[r].append((left, right))\n\telse:\n\t\ttrains[r] = [(left, right)]\n\ndef merge(tracks, i):\n\tif i >= len(tracks):\n\t\treturn (-1, 0, 0)\n\telse:\n\t\tleft = tracks[i][0]\n\t\tright = tracks[i][1]\n\t\tfor j in range(i + 1, len(tracks)):\n\t\t\tif tracks[j][0] > right:\n\t\t\t\treturn (j, left, right)\n\t\t\telse:\n\t\t\t\tright = max(right, tracks[j][1])\n\t\treturn (k, left, right)\noccupiedCells = 0\nfor r in trains:\n\ttracks = trains[r]\n\ttracks.sort(key=lambda x: x[0])\n\ti = 0\n\twhile i < k:\n\t\tresult = merge(tracks, i)\n\t\ti = result[0]\n\t\tif i != -1:\n\t\t\toccupiedCells += result[2] - result[1] + 1\nprint(n * m - occupiedCells)\n", "(n, m, k) = input().strip().split(' ')\n(n, m, k) = (int(n), int(m), int(k))\n\ndef insert(l, a, b):\n\tstart = -1\n\tend = len(l)\n\tfor i in range(len(l)):\n\t\tif a > l[i]:\n\t\t\tstart = i\n\t\tif b < l[i]:\n\t\t\tend = i\n\t\t\tbreak\n\treturn l[:start + 1] + [a] * (start % 2) + [b] * ((end + 1) % 2) + l[end:]\ndct = {}\nfor train_track in range(k):\n\t(r, c1, c2) = input().strip().split(' ')\n\t(r, c1, c2) = (int(r), int(c1), int(c2))\n\tdct[r] = insert(dct.get(r, []), c1, c2)\ntotal = n * m\nfor v in dct.values():\n\tfor j in range(0, len(v), 2):\n\t\ttotal -= v[j + 1] - v[j] + 1\nprint(total)\n", "from operator import itemgetter\n(n, m, k) = map(int, input().split(' '))\ng_ = [tuple(map(int, input().split(' '))) for i in range(k)]\ng = sorted(g_, key=itemgetter(0, 1, 2))\ntracks = {}\n\ndef squidge(row):\n\tflag = False\n\tfor (i, cur) in enumerate(row):\n\t\tif i == 0:\n\t\t\tcontinue\n\t\t(c1, c2) = cur\n\t\t(xc1, xc2) = row[i - 1]\n\t\tif c2 <= xc2:\n\t\t\tdel row[i]\n\t\t\tflag = True\n\t\t\tbreak\n\t\tif c1 <= xc2:\n\t\t\trow[i - 1][1] = c2\n\t\t\tdel row[i]\n\t\t\tflag = True\n\t\t\tbreak\n\tif flag:\n\t\tsquidge(row)\nfor (r, c1, c2) in g:\n\tif r not in tracks:\n\t\ttracks[r] = [[c1, c2]]\n\telse:\n\t\ttracks[r].append([c1, c2])\nfor r in tracks:\n\tsquidge(tracks[r])\ntaken = 0\nfor r in tracks:\n\tfor t in tracks[r]:\n\t\ttaken += t[1] - t[0] + 1\nprint(n * m - taken)\n", "class track:\n\n\tdef __init__(self):\n\t\tself.start = -1\n\t\tself.stop = -1\n\t\tself.next = None\n\ndef printInsert(before, after):\n\tprint('Insert between <', end='')\n\tif before == None:\n\t\tprint('None', end='')\n\telse:\n\t\tprint(before.start, ':', before.stop, end='')\n\tprint('> and <', end='')\n\tif after == None:\n\t\tprint('None', end='')\n\telse:\n\t\tprint(after.start, ':', after.stop, end='')\n\tprint('>')\n\ndef insertTrack(t, a, b):\n\tbefore = None\n\tafter = t\n\thead = t\n\taddNew = True\n\twhile True:\n\t\tif after == None:\n\t\t\tbreak\n\t\tif before == None and b <= after.stop:\n\t\t\tbreak\n\t\tif a < after.start:\n\t\t\tbreak\n\t\tbefore = after\n\t\tafter = after.next\n\tif after != None and a >= after.start and (b <= after.stop):\n\t\treturn head\n\tif before != None and a <= before.stop + 1:\n\t\taddNew = False\n\t\tbefore.stop = b\n\tif addNew:\n\t\tnewT = track()\n\t\tnewT.start = a\n\t\tnewT.stop = b\n\t\tnewT.next = after\n\t\tif before == None:\n\t\t\thead = newT\n\t\telse:\n\t\t\tbefore.next = newT\n\t\tbefore = newT\n\twhile after != None and b >= after.start - 1:\n\t\tbefore.next = after.next\n\t\tif b > after.stop:\n\t\t\tbefore.stop = b\n\t\telse:\n\t\t\tbefore.stop = after.stop\n\t\tafter = before.next\n\treturn head\n\ndef printTracks(t):\n\tprint('--- BEGIN ---')\n\twhile t != None:\n\t\tprint(t.start, ':', t.stop)\n\t\tt = t.next\n\tprint('--- END ---')\n\tprint()\n\ndef testInput():\n\tt = None\n\twhile True:\n\t\tinpSplit = input().split()\n\t\ta = int(inpSplit[0])\n\t\tb = int(inpSplit[1])\n\t\tt = insertTrack(t, a, b)\n\t\tprintTracks(t)\ninpSplit = input().split()\nrowCount = int(inpSplit[0])\ncolCount = int(inpSplit[1])\ntrackCount = int(inpSplit[2])\ntracks = {}\nfor i in range(0, trackCount):\n\tinpSplit = input().split()\n\trow = int(inpSplit[0])\n\tcolStart = int(inpSplit[1])\n\tcolEnd = int(inpSplit[2])\n\tif row not in tracks:\n\t\ttracks[row] = None\n\ttracks[row] = insertTrack(tracks[row], colStart, colEnd)\nsum = 0\ndictionaryRowCount = 0\nfor key in tracks:\n\tt = tracks[key]\n\trowSum = colCount\n\twhile t != None:\n\t\trowSum -= t.stop - t.start + 1\n\t\tt = t.next\n\tsum += rowSum\n\tdictionaryRowCount += 1\nsum += (rowCount - dictionaryRowCount) * colCount\nprint(sum)\n", "def checkTrackRange(oldVals, start, end):\n\tnewRange = list()\n\tif oldVals[0] <= start and start <= oldVals[1] or (start <= oldVals[0] and oldVals[0] <= end):\n\t\ts = min(oldVals[0], start)\n\tif oldVals[0] <= end and end <= oldVals[1] or (start <= oldVals[1] and oldVals[1] <= end):\n\t\te = max(oldVals[1], end)\n\tif oldVals[1] < start or start < oldVals[0]:\n\t\treturn None\n\tnewRange.append(s)\n\tnewRange.append(e)\n\treturn newRange\n\ndef getRangesum(hashMap):\n\tsum = 0\n\tfor (k, v) in hashMap.items():\n\t\ti = 0\n\t\twhile i <= len(v) - 2:\n\t\t\tsum += abs(v[i] - v[i + 1]) + 1\n\t\t\ti += 2\n\treturn sum\n\ndef generateRestCellCount(tracks):\n\thashMap = dict()\n\tfor line in tracks:\n\t\tvals = line.split(' ')\n\t\tif len(vals) == 3:\n\t\t\tk = int(vals[0])\n\t\t\tif k in hashMap:\n\t\t\t\toldVals = hashMap[k]\n\t\t\t\tif oldVals is not None:\n\t\t\t\t\tnewRange = checkTrackRange(oldVals, int(vals[1]), int(vals[2]))\n\t\t\t\t\tif newRange is None:\n\t\t\t\t\t\toldVals.append(int(vals[1]))\n\t\t\t\t\t\toldVals.append(int(vals[2]))\n\t\t\t\t\t\thashMap[k] = oldVals\n\t\t\t\t\telse:\n\t\t\t\t\t\thashMap[k] = newRange\n\t\t\telse:\n\t\t\t\tnewRange = [int(vals[1]), int(vals[2])]\n\t\t\t\thashMap[k] = newRange\n\tsum = getRangesum(hashMap)\n\treturn sum\n(n, m, k) = input().strip().split(' ')\ntracks = list()\nfor i in range(int(k)):\n\ttrack = input().strip()\n\ttracks.append(track)\nsum = generateRestCellCount(tracks)\nrestCellCount = int(n) * int(m) - sum\nif restCellCount > 0:\n\tprint(restCellCount)\nelse:\n\tprint(0)\n", "(n, m, k) = map(int, input().split())\nrows = {}\nfor i in range(k):\n\t(x, y1, y2) = map(int, input().split())\n\tif x in rows:\n\t\trows[x].append([y1, y2])\n\telse:\n\t\trows[x] = [[y1, y2]]\nfor row in rows:\n\tjoined = []\n\tcurr = sorted(rows[row], key=lambda x: (x[0], m - x[1]))[0]\n\tfor i in range(1, len(rows[row])):\n\t\tif rows[row][i][0] <= curr[1]:\n\t\t\tcurr[1] = max(rows[row][i][1], curr[1])\n\t\telse:\n\t\t\tjoined.append(curr)\n\t\t\tcurr = rows[row][i]\n\tjoined.append(curr)\n\trows[row] = joined\nans = (n - len(rows)) * m\nfor row in rows:\n\tk = 0\n\tfor segment in rows[row]:\n\t\tk += segment[1] - segment[0] + 1\n\tans += m - k\nprint(ans)\n", "from collections import defaultdict\nfrom operator import itemgetter\n(n, m, k) = map(int, input().split())\ntracks = []\nif k == 0:\n\tprint(n * m)\nelif k == 1:\n\t(row, start, end) = map(int, input().split())\n\tprint(n * m - (end - start))\nelse:\n\tfor __ in range(k):\n\t\t(row, start, end) = map(int, input().split())\n\t\ttracks.append([row, (start, end)])\n\ttracks = sorted(tracks, key=itemgetter(0))\n\tmerged_tracks = defaultdict(list)\n\tfor track in tracks:\n\t\tmerged_tracks[track[0]] += [track[1]]\n\trows = sorted(merged_tracks)\n\trow_expected = 1\n\tfree_space = n * m\n\tfor row in rows:\n\t\tcrazy_tracks = sorted(merged_tracks[row])\n\t\tvalid_tracks = []\n\t\tfor crazy_track in crazy_tracks:\n\t\t\tstart = crazy_track[0]\n\t\t\tend = crazy_track[1]\n\t\t\tif not valid_tracks:\n\t\t\t\tvalid_tracks.append((start, end))\n\t\t\t\tcontinue\n\t\t\treplaced = False\n\t\t\tfor index in range(len(valid_tracks)):\n\t\t\t\tv_track = valid_tracks[index]\n\t\t\t\tv_start = v_track[0]\n\t\t\t\tv_end = v_track[1]\n\t\t\t\tif start <= v_start:\n\t\t\t\t\tif end <= v_end and end > v_end:\n\t\t\t\t\t\tvalid_tracks[index] = (start, v_end)\n\t\t\t\t\t\treplaced = True\n\t\t\t\t\telif end >= v_end:\n\t\t\t\t\t\tvalid_tracks[index] = (start, end)\n\t\t\t\t\t\treplaced = True\n\t\t\t\telif start > v_start and start <= v_end:\n\t\t\t\t\tif end <= v_end:\n\t\t\t\t\t\treplaced = True\n\t\t\t\t\t\tcontinue\n\t\t\t\t\telif end >= v_end:\n\t\t\t\t\t\tvalid_tracks[index] = (v_start, end)\n\t\t\t\t\t\treplaced = True\n\t\t\tif not replaced:\n\t\t\t\tvalid_tracks.append((start, end))\n\t\tspace_taken = 0\n\t\tfor track in valid_tracks:\n\t\t\tspace_taken += track[1] - track[0] + 1\n\t\tfree_space -= space_taken\n\tprint(free_space)\n", "(n, m, k) = map(int, input().split())\nrs = {}\nfor _ in range(k):\n\t(r, cs, ce) = map(int, input().split())\n\trs.setdefault(r, []).append((cs, ce))\nresult = (n - len(rs)) * m\nfor trains in rs.values():\n\ttrains.sort()\n\tlast = 0\n\tfor (start, end) in trains:\n\t\tif start > last + 1:\n\t\t\tresult += start - last - 1\n\t\tlast = max(last, end)\n\tresult += m - last\nprint(result)\n", "(n, m, k) = map(int, input().split())\ntracks = [list(map(int, input().split())) for _ in range(k)]\ntracks.sort()\ni = 1\nactive = 0\ndisabled = [False] * k\nwhile i < len(tracks):\n\tif tracks[active][0] == tracks[i][0] and tracks[i][1] <= tracks[active][2]:\n\t\tdisabled[i] = True\n\t\ttracks[active][2] = max(tracks[i][2], tracks[active][2])\n\telse:\n\t\tactive = i\n\ti += 1\nprint(n * m - sum((tracks[i][2] - tracks[i][1] + 1 for i in range(k) if not disabled[i])))\n", "import sys\nfrom operator import itemgetter\n\ndef counter(lst):\n\tlst.sort(key=itemgetter(0))\n\ti = 0\n\twhile i < len(lst) - 1:\n\t\tfirst = lst[i]\n\t\tsecond = lst[i + 1]\n\t\tif second[0] <= first[1]:\n\t\t\tlst.remove(first)\n\t\t\tlst.remove(second)\n\t\t\tlst.insert(i, [first[0], max(first[1], second[1])])\n\t\telse:\n\t\t\ti += 1\n\tcount = 0\n\tfor item in lst:\n\t\tcount += item[1] - item[0] + 1\n\treturn count\ntri = list(map(int, input().strip().split(' ')))\n(n, m, k) = (tri[0], tri[1], tri[2])\ndct = {}\nrowlist = []\nrowcount = 0\nfor _ in range(k):\n\ttri = list(map(int, input().strip().split(' ')))\n\trow = tri[0]\n\tc1 = tri[1]\n\tc2 = tri[2]\n\tif dct.get(row) == None:\n\t\tdct[row] = [[c1, c2]]\n\t\trowlist.append(row)\n\t\trowcount += 1\n\telse:\n\t\tdct[row].append([c1, c2])\ncount = (n - rowcount) * m\nfor item in rowlist:\n\tcount += m - counter(dct[item])\nprint(count)\n", "(n, m, k) = input().split(' ', 2)\n(n, m, k) = (int(n), int(m), int(k))\nlst = []\nlst2 = []\ngraph = {}\nfor i in range(0, k):\n\t(r, c1, c2) = input().split(' ', 2)\n\t(r, c1, c2) = (int(r), int(c1), int(c2))\n\tlst.append([r - 1, c1, c2])\n\tgraph[int(r) - 1] = []\nfor i in range(0, k):\n\tindex = 0\n\tflag = 0\n\tflag2 = 0\n\tfor j in range(0, len(graph[lst[i][0]])):\n\t\tif lst[i][1] > graph[lst[i][0]][j][0]:\n\t\t\tpass\n\t\telse:\n\t\t\tif lst[i][1] == graph[lst[i][0]][j][0]:\n\t\t\t\tgraph[lst[i][0]][j][1] = max(graph[lst[i][0]][j][1], lst[i][2])\n\t\t\t\tflag2 = 1\n\t\t\tindex = j\n\t\t\tflag = 1\n\t\t\tbreak\n\tif flag == 0:\n\t\tindex = len(graph[lst[i][0]])\n\tif flag2 == 0:\n\t\tgraph[lst[i][0]].insert(index, [lst[i][1], lst[i][2]])\nfor item in graph:\n\tj = 0\n\twhile True:\n\t\tif j < len(graph[item]) - 1:\n\t\t\tif graph[item][j + 1][0] <= graph[item][j][1] + 1:\n\t\t\t\tif graph[item][j + 1][1] > graph[item][j][1]:\n\t\t\t\t\tgraph[item][j][1] = graph[item][j + 1][1]\n\t\t\t\tgraph[item].pop(j + 1)\n\t\t\t\tj -= 1\n\t\telse:\n\t\t\tbreak\n\t\tj += 1\ncount = 0\nfor item in graph:\n\tfor j in range(0, len(graph[item])):\n\t\tcount += graph[item][j][1] - graph[item][j][0] + 1\nprint(m * n - count)\n", "def findlampposts(tracks, n, m):\n\tposts = m * n\n\ttracks = sorted(tracks, key=lambda x: (x[0], x[1], x[2]))\n\tr = 0\n\tcr = 0\n\tfor t in tracks:\n\t\tif t[0] == r:\n\t\t\tif t[1] > cr:\n\t\t\t\tposts -= 1 + t[2] - t[1]\n\t\t\telif t[2] <= cr:\n\t\t\t\tpass\n\t\t\telse:\n\t\t\t\tposts -= t[2] - cr\n\t\telse:\n\t\t\tcr = 0\n\t\t\tr = t[0]\n\t\t\tposts -= 1 + t[2] - t[1]\n\t\tif t[2] > cr:\n\t\t\tcr = t[2]\n\treturn posts\n\ndef main():\n\t(n, m, k) = tuple([int(x) for x in input().strip().split(' ')])\n\ttracks = []\n\tfor i in range(k):\n\t\ttracks.append([int(x) for x in input().strip().split(' ')])\n\tprint('%d' % (findlampposts(tracks, n, m),))\nmain()\n", "import sys\n(m, n, k) = [int(i) for i in input().strip().split()]\nKC1C2 = [[int(i) for i in line.strip().split()] for line in sys.stdin.readlines()]\n\ndef mergeRailSegments(allSegList):\n\tallSegList.sort(key=lambda x: x[0])\n\tnonOverlapSegmentsList = [allSegList[0]]\n\tfor seg in allSegList[1:]:\n\t\tfor i in range(len(nonOverlapSegmentsList)):\n\t\t\tnoseg = nonOverlapSegmentsList[i]\n\t\t\tif seg[0] <= noseg[1]:\n\t\t\t\tnewNoseg = (noseg[0], max(seg[1], noseg[1]))\n\t\t\t\tnonOverlapSegmentsList[i] = newNoseg\n\t\t\t\tbreak\n\t\t\telif i == len(nonOverlapSegmentsList) - 1:\n\t\t\t\tnonOverlapSegmentsList.append(seg)\n\t\t\telse:\n\t\t\t\tcontinue\n\treturn nonOverlapSegmentsList\n\ndef recurMerge(segList):\n\tif len(segList) == 1:\n\t\treturn segList\n\telse:\n\t\tsegList.sort(key=lambda x: x[0])\n\t\tnumOverlappingSegs = sum([segList[i][1] >= segList[i + 1][0] for i in range(len(segList) - 1)])\n\t\tif numOverlappingSegs == 0:\n\t\t\treturn segList\n\t\telse:\n\t\t\tmergedSegList = mergeRailSegments(segList)\n\t\t\treturn recurMerge(mergedSegList)\n\ndef sumSegLengths(nonOverlappingSegList):\n\treturn sum([seg[1] - seg[0] + 1 for seg in nonOverlappingSegList])\nrailrowSet = set([railrow[0] for railrow in KC1C2])\nd = {r: [(row[1], row[2]) for row in KC1C2 if row[0] == r] for r in railrowSet}\nrailSquares = sum([sumSegLengths(recurMerge(d[key])) for key in d])\nprint(m * n - railSquares)\n", "s1 = input().split(' ')\nn = int(s1[0])\nm = int(s1[1])\ntrains = int(s1[2])\ntrain_info = dict()\nfor i in range(trains):\n\tchar_arr = input().split(' ')\n\trow = int(char_arr[0])\n\tstart = int(char_arr[1])\n\tend = int(char_arr[2])\n\tif row in train_info:\n\t\tinfo = train_info[row]\n\t\tfor j in info:\n\t\t\tif j[0] <= start <= j[1] or j[0] <= end <= j[1]:\n\t\t\t\tstart = min(start, j[0])\n\t\t\t\tend = max(end, j[1])\n\t\t\t\ttrain_info[row].remove(j)\n\t\t\t\tbreak\n\t\ttrain_info[row].append([start, end])\n\telse:\n\t\ttrain_info[row] = [[int(char_arr[1]), int(char_arr[2])]]\ncount = 0\nfor (k, v) in train_info.items():\n\tfor j in v:\n\t\tcount += j[1] - j[0] + 1\nprint(n * m - count)\n", "def add(key, start, end):\n\tto_remove = []\n\tno_add = False\n\tfor tup in row_map[key]:\n\t\tif tup[1] >= end and start <= tup[0] and (end >= tup[0]):\n\t\t\tend = tup[1]\n\t\t\tto_remove.append(tup)\n\t\telif tup[1] <= end and start >= tup[0] and (start <= tup[1]):\n\t\t\tstart = tup[0]\n\t\t\tto_remove.append(tup)\n\t\telif start <= tup[0] and end >= tup[1]:\n\t\t\tto_remove.append(tup)\n\t\telif tup[1] >= end and tup[0] <= start:\n\t\t\tno_add = True\n\tif to_remove:\n\t\tfor tup in to_remove:\n\t\t\trow_map[key].remove(tup)\n\tif not no_add:\n\t\trow_map[key].append((start, end))\ns_len = input().strip()\nrow_map = {}\nx = [int(i) for i in s_len.split()]\ntracks = x[2]\ntotal = x[0] * x[1]\nfor i in range(tracks):\n\tt = input().strip()\n\ts = [int(i) for i in t.split()]\n\ttry:\n\t\trow_map[s[0]]\n\t\tadd(s[0], s[1], s[2])\n\texcept KeyError:\n\t\trow_map[s[0]] = [(s[1], s[2])]\ncount = 0\nfor key in row_map:\n\ttest = 0\n\trange_lis = []\n\tj = 0\n\tfor tup in row_map[key]:\n\t\trange_lis.append(tup[0])\n\t\trange_lis.append(tup[1])\n\trange_lis = sorted(range_lis)\n\tfor i in range(0, len(range_lis), 2):\n\t\ttest += range_lis[i + 1] - range_lis[i] + 1\n\t\tcount += range_lis[i + 1] - range_lis[i] + 1\nans = total - count\nprint(ans)\n", "def overlapped(c1, c2, g1, g2):\n\tif c1 == g2 + 1 or g1 == c2 + 1:\n\t\treturn True\n\telif g1 <= c1 <= g2 or g1 <= c2 <= g2:\n\t\treturn True\n\telif c1 <= g1 <= c2 or c1 <= g2 <= c2:\n\t\treturn True\n\ndef update_gridland(r, c1, c2):\n\tif r not in gridland:\n\t\tgridland[r] = []\n\t\tgridland[r].append((c1, c2))\n\telse:\n\t\ttrackadded = False\n\t\tfor i in range(len(gridland[r])):\n\t\t\tif overlapped(c1, c2, gridland[r][i][0], gridland[r][i][1]):\n\t\t\t\tgridland[r][i] = (min(c1, gridland[r][i][0]), max(c2, gridland[r][i][1]))\n\t\t\t\ttrackadded = True\n\t\t\t\tbreak\n\t\tif not trackadded:\n\t\t\tgridland[r].append((c1, c2))\n(n, m, k) = list(map(int, input().strip().split()))\ntracks = []\nfor i in range(k):\n\ttracks.append(tuple(map(int, input().strip().split())))\ntracks = tuple(tracks)\ngridland = {}\nfor t in tracks:\n\t(r, c1, c2) = t\n\tupdate_gridland(r, c1, c2)\nused = 0\nfor row in gridland:\n\tfor tracks in gridland[row]:\n\t\tused += abs(tracks[0] - tracks[1]) + 1\nprint(n * m - used)\n"]

difficulty: MEDIUM

source: hacker rank

skill_types: ['Complete search']

question:
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:

![image](1.png)
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

![image](2.png)
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.

image_tags: Map Map

data_split: test


G. Mergesort Strikes Back

problem_index: G

time_limit: 1 second

memory_limit: 256 megabytes

source: codeforces

raw_problem:
G. Mergesort Strikes Back

time limit per test
1 second

memory limit per test
256 megabytes

input
standard input

output
standard output

Chouti thought about his very first days in competitive programming. When he had just learned to write merge sort, he thought that the merge sort is too slow, so he restricted the maximum depth of recursion and modified the merge sort to the following:

Chouti found his idea dumb since obviously, this "merge sort" sometimes cannot sort the array correctly. However, Chouti is now starting to think of how good this "merge sort" is. Particularly, Chouti wants to know for a random permutation $$$a$$$ of $$$1, 2, \ldots, n$$$ the expected number of inversions after calling MergeSort(a, 1, n, k).

It can be proved that the expected number is rational. For the given prime $$$q$$$, suppose the answer can be denoted by $$$\frac{u}{d}$$$ where $$$gcd(u,d)=1$$$, you need to output an integer $$$r$$$ satisfying $$$0 \le r<q$$$ and $$$rd \equiv u \pmod q$$$. It can be proved that such $$$r$$$ exists and is unique.

Input

The first and only line contains three integers $$$n, k, q$$$ ($$$1 \leq n, k \leq 10^5, 10^8 \leq q \leq 10^9$$$, $$$q$$$ is a prime).

Output

The first and only line contains an integer $$$r$$$.

Examples

Input

3 1 998244353

Output

499122178

Input

3 2 998244353

Output

665496236

Input

9 3 998244353

Output

449209967

Input

9 4 998244353

Output

665496237

Note

In the first example, all possible permutations are $$$[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]$$$.

With $$$k=1$$$, MergeSort(a, 1, n, k) will only return the original permutation. Thus the answer is $$$9/6=3/2$$$, and you should output $$$499122178$$$ because $$$499122178 \times 2 \equiv 3 \pmod {998244353}$$$.

In the second example, all possible permutations are $$$[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]$$$ and the corresponding outputs of MergeSort(a, 1, n, k) are $$$[1,2,3],[1,2,3],[2,1,3],[1,2,3],[2,3,1],[1,3,2]$$$ respectively. Thus the answer is $$$4/6=2/3$$$, and you should output $$$665496236$$$ because $$$665496236 \times 3 \equiv 2 \pmod {998244353}$$$.

question:
Chouti thought about his very first days in competitive programming. When he had just learned to write merge sort, he thought that the merge sort is too slow, so he restricted the maximum depth of recursion and modified the merge sort to the following:
 ![image](1.png) Chouti found his idea dumb since obviously, this "merge sort" sometimes cannot sort the array correctly. However, Chouti is now starting to think of how good this "merge sort" is. Particularly, Chouti wants to know for a random permutation $$$a$$$ of $$$1, 2, \ldots, n$$$ the expected number of inversions after calling MergeSort(a, 1, n, k).
It can be proved that the expected number is rational. For the given prime $$$q$$$, suppose the answer can be denoted by $$$\frac{u}{d}$$$ where $$$gcd(u,d)=1$$$, you need to output an integer $$$r$$$ satisfying $$$0 \le r<q$$$ and $$$rd \equiv u \pmod q$$$. It can be proved that such $$$r$$$ exists and is unique.

Input
The first and only line contains three integers $$$n, k, q$$$ ($$$1 \leq n, k \leq 10^5, 10^8 \leq q \leq 10^9$$$, $$$q$$$ is a prime).

Output
The first and only line contains an integer $$$r$$$.

Examples
Input
3 1 998244353

Output
499122178

Input
3 2 998244353

Output
665496236

Input
9 3 998244353

Output
449209967

Input
9 4 998244353

Output
665496237

Note
In the first example, all possible permutations are $$$[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]$$$.
With $$$k=1$$$, MergeSort(a, 1, n, k) will only return the original permutation. Thus the answer is $$$9/6=3/2$$$, and you should output $$$499122178$$$ because $$$499122178 \times 2 \equiv 3 \pmod {998244353}$$$.
In the second example, all possible permutations are $$$[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]$$$ and the corresponding outputs of MergeSort(a, 1, n, k) are $$$[1,2,3],[1,2,3],[2,1,3],[1,2,3],[2,3,1],[1,3,2]$$$ respectively. Thus the answer is $$$4/6=2/3$$$, and you should output $$$665496236$$$ because $$$665496236 \times 3 \equiv 2 \pmod {998244353}$$$.

data_split: test


E. Caramel Clouds

problem_index: E

time_limit: 3 seconds

memory_limit: 256 megabytes

note:
Consider the first example. For each k it is optimal to dispel clouds 1 and 3. Then the remaining cloud will give shadow on time segment [1..6]. So, intervals [0..1] and [6..inf) are sunny.
![image](images/cf_833_E/2.png)
In the second example for k = 1 it is not necessary to dispel anything, and for k = 5 the best strategy is to dispel clouds 2 and 3. This adds an additional sunny segment [4..8], which together with [0..1] allows to grow up the muffin at the eight minute.
![image](images/cf_833_E/3.png) ![image](images/cf_833_E/4.png)
If the third example the two seedlings are completely different. For the first one it is necessary to dispel cloud 1 and obtain a sunny segment [0..10]. However, the same strategy gives answer 180 for the second seedling. Instead, we can dispel cloud 2, to make segments [0..3] and [7..inf) sunny, and this allows up to shorten the time to 104.

source: codeforces

raw_problem:
E. Caramel Clouds

time limit per test
3 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

It is well-known that the best decoration for a flower bed in Sweetland are vanilla muffins. Seedlings of this plant need sun to grow up. Slastyona has m seedlings, and the j-th seedling needs at least kj minutes of sunlight to grow up.

Most of the time it's sunny in Sweetland, but sometimes some caramel clouds come, the i-th of which will appear at time moment (minute) li and disappear at time moment ri. Of course, the clouds make shadows, and the seedlings can't grow when there is at least one cloud veiling the sun.

Slastyona wants to grow up her muffins as fast as possible. She has exactly C candies, which is the main currency in Sweetland.

One can dispel any cloud by paying ci candies. However, in order to comply with Sweetland's Department of Meteorology regulations, one can't dispel more than two clouds.

Slastyona hasn't decided yet which of the m seedlings will be planted at the princess' garden, so she needs your help. For each seedling determine the earliest moment it can grow up if Slastyona won't break the law and won't spend more candies than she has. Note that each of the seedlings is considered independently.

The seedlings start to grow at time moment 0.

Input

The first line contains two integers n and C (0 ≤ n ≤ 3·105, 0 ≤ C ≤ 109) – the number of caramel clouds and the number of candies Slastyona has.

The next n lines contain three integers each: li, ri, ci (0 ≤ li < ri ≤ 109, 0 ≤ ci ≤ 109), describing one caramel cloud.

The next line contains single integer m (1 ≤ m ≤ 3·105) – the number of seedlings. Each of the seedlings is described with one integer kj (1 ≤ kj ≤ 109) – the required number of sunny minutes.

Output

For each seedling print one integer – the minimum minute Slastyona can grow it up.

Examples

Input

3 5
1 7 1
1 6 2
1 7 1
3
7
2
5

Output

12
7
10

Input

3 15
1 4 17
2 8 6
4 8 9
2
5
1

Output

8
1

Input

2 10
3 7 9
10 90 10
2
10
100

Output

10
104

Note

Consider the first example. For each k it is optimal to dispel clouds 1 and 3. Then the remaining cloud will give shadow on time segment [1..6]. So, intervals [0..1] and [6..inf) are sunny.

In the second example for k = 1 it is not necessary to dispel anything, and for k = 5 the best strategy is to dispel clouds 2 and 3. This adds an additional sunny segment [4..8], which together with [0..1] allows to grow up the muffin at the eight minute.

If the third example the two seedlings are completely different. For the first one it is necessary to dispel cloud 1 and obtain a sunny segment [0..10]. However, the same strategy gives answer 180 for the second seedling. Instead, we can dispel cloud 2, to make segments [0..3] and [7..inf) sunny, and this allows up to shorten the time to 104.

question:
It is well-known that the best decoration for a flower bed in Sweetland are vanilla muffins. Seedlings of this plant need sun to grow up. Slastyona has m seedlings, and the j-th seedling needs at least k_{j} minutes of sunlight to grow up.
Most of the time it's sunny in Sweetland, but sometimes some caramel clouds come, the i-th of which will appear at time moment (minute) l_{i} and disappear at time moment r_{i}. Of course, the clouds make shadows, and the seedlings can't grow when there is at least one cloud veiling the sun.
Slastyona wants to grow up her muffins as fast as possible. She has exactly C candies, which is the main currency in Sweetland.
One can dispel any cloud by paying c_{i} candies. However, in order to comply with Sweetland's Department of Meteorology regulations, one can't dispel more than two clouds.
Slastyona hasn't decided yet which of the m seedlings will be planted at the princess' garden, so she needs your help. For each seedling determine the earliest moment it can grow up if Slastyona won't break the law and won't spend more candies than she has. Note that each of the seedlings is considered independently.
The seedlings start to grow at time moment 0.

Input
The first line contains two integers n and C (0 ≤ n ≤ 3·10^{5}, 0 ≤ C ≤ 10^{9}) – the number of caramel clouds and the number of candies Slastyona has.
The next n lines contain three integers each: l_{i}, r_{i}, c_{i} (0 ≤ l_{i} < r_{i} ≤ 10^{9}, 0 ≤ c_{i} ≤ 10^{9}), describing one caramel cloud.
The next line contains single integer m (1 ≤ m ≤ 3·10^{5}) – the number of seedlings. Each of the seedlings is described with one integer k_{j} (1 ≤ k_{j} ≤ 10^{9}) – the required number of sunny minutes.

Output
For each seedling print one integer – the minimum minute Slastyona can grow it up.

Examples
Input
3 5
1 7 1
1 6 2
1 7 1
3
7
2
5

Output
12
7
10

Input
3 15
1 4 17
2 8 6
4 8 9
2
5
1

Output
8
1

Input
2 10
3 7 9
10 90 10
2
10
100

Output
10
104

Note
Consider the first example. For each k it is optimal to dispel clouds 1 and 3. Then the remaining cloud will give shadow on time segment [1..6]. So, intervals [0..1] and [6..inf) are sunny.
 ![image](2.png) In the second example for k = 1 it is not necessary to dispel anything, and for k = 5 the best strategy is to dispel clouds 2 and 3. This adds an additional sunny segment [4..8], which together with [0..1] allows to grow up the muffin at the eight minute.
 ![image](3.png) ![image](4.png) If the third example the two seedlings are completely different. For the first one it is necessary to dispel cloud 1 and obtain a sunny segment [0..10]. However, the same strategy gives answer 180 for the second seedling. Instead, we can dispel cloud 2, to make segments [0..3] and [7..inf) sunny, and this allows up to shorten the time to 104.

tags: ['Dynamic programming', 'Sorting', 'Data structures']

image_tags:
Linear Data Structure
Linear Data Structure
Linear Data Structure

data_split: test