There is a square of size $10^6 \times 10^6$ on the coordinate plane with four points $(0, 0)$, $(0, 10^6)$, $(10^6, 0)$, and $(10^6, 10^6)$ as its vertices.

You are going to draw segments on the plane. All segments are either horizontal or vertical and intersect with at least one side of the square.

Now you are wondering how many pieces this square divides into after drawing all segments. Write a program calculating the number of pieces of the square.


-----Input-----

The first line contains two integers $n$ and $m$ ($0 \le n, m \le 10^5$) — the number of horizontal segments and the number of vertical segments.

The next $n$ lines contain descriptions of the horizontal segments. The $i$-th line contains three integers $y_i$, $lx_i$ and $rx_i$ ($0 < y_i < 10^6$; $0 \le lx_i < rx_i \le 10^6$), which means the segment connects $(lx_i, y_i)$ and $(rx_i, y_i)$.

The next $m$ lines contain descriptions of the vertical segments. The $i$-th line contains three integers $x_i$, $ly_i$ and $ry_i$ ($0 < x_i < 10^6$; $0 \le ly_i < ry_i \le 10^6$), which means the segment connects $(x_i, ly_i)$ and $(x_i, ry_i)$.

It's guaranteed that there are no two segments on the same line, and each segment intersects with at least one of square's sides.


-----Output-----

Print the number of pieces the square is divided into after drawing all the segments.


-----Example-----
Input
3 3
2 3 1000000
4 0 4
3 0 1000000
4 0 1
2 0 5
3 1 1000000

Output
7


-----Note-----

 The sample is like this: [Image]

Difficulty: MEDIUM

Starter code:

Solutions:
import sys
from collections import deque
from queue import PriorityQueue
from math import gcd
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
(n, m) = il()
a = []
ans = 1
for _ in range(n):
	(y, lx, ly) = il()
	a.append([3 * y + 1, [lx, ly]])
	if ly - lx == 10 ** 6:
		ans += 1
for _ in range(m):
	(x, ly, ry) = il()
	a.append([3 * ly, x])
	a.append([3 * ry + 2, x])
	if ry - ly == 10 ** 6:
		ans += 1
m = 10 ** 6 + 5

def sum(i):
	s = 0
	while i > 0:
		s += fin[i]
		i -= i & -i
	return s

def add(i, x):
	while i <= m:
		fin[i] += x
		i += i & -i
a.sort()
fin = [0 for i in range(10 ** 6 + 5)]
for i in range(len(a)):
	(y, x) = (a[i][0], a[i][1])
	if y % 3 == 1:
		ans += sum(x[1]) - sum(x[0] - 1)
	elif y % 3 == 0:
		add(x, 1)
	else:
		add(x, -1)
print(ans)


import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, m) = map(int, input().split())
INF = 10 ** 18
ans = 1
H = []
ys = []
for i in range(n):
	(y, lx, rx) = map(int, input().split())
	if lx == 0 and rx == 10 ** 6:
		ans += 1
	H.append((lx, y, 1))
	H.append((rx + 1, y, -1))
	ys.append(y)
V = []
for i in range(m):
	(x, ly, ry) = map(int, input().split())
	if ly == 0 and ry == 10 ** 6:
		ans += 1
	V.append((x, ly, ry))
ys = list(set(ys))
ys.sort()
ys = [-INF] + ys
ymap = {}
for (i, y) in enumerate(ys):
	ymap[y] = i

class BIT:

	def __init__(self, n):
		self.n = n
		self.bit = [0] * (self.n + 1)

	def init(self, init_val):
		for (i, v) in enumerate(init_val):
			self.add(i, v)

	def add(self, i, x):
		i += 1
		while i <= self.n:
			self.bit[i] += x
			i += i & -i

	def sum(self, i, j):
		return self._sum(j) - self._sum(i)

	def _sum(self, i):
		res = 0
		while i > 0:
			res += self.bit[i]
			i -= i & -i
		return res

	def lower_bound(self, x):
		s = 0
		pos = 0
		depth = self.n.bit_length()
		v = 1 << depth
		for i in range(depth, -1, -1):
			k = pos + v
			if k <= self.n and s + self.bit[k] < x:
				s += self.bit[k]
				pos += v
			v >>= 1
		return pos
V.sort()
H.sort()
hid = 0
nh = len(H)
nv = len(ys)
bit = BIT(nv + 1)
import bisect
for (x, ly, ry) in V:
	while hid < nh:
		if H[hid][0] <= x:
			bit.add(ymap[H[hid][1]], H[hid][2])
			hid += 1
		else:
			break
	l = bisect.bisect_left(ys, ly)
	r = bisect.bisect_right(ys, ry)
	ans += bit.sum(l, r)
print(ans)


import sys, math
import io, os
data = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
from decimal import Decimal
INF = float('inf')
mod = int(1000000000.0) + 7

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))
(n, m) = mdata()
hor = [mdata() for i in range(n)]
ver = [mdata() for i in range(m)]
topVer = SortedList()
botVer = SortedList()
ans = 1
for (x, bot, top) in ver:
	if bot == 0:
		botVer.add(x)
		if top == 10 ** 6:
			ans += 1
	else:
		topVer.add(x)
hor.sort(key=lambda x: x[0], reverse=True)
ver.sort(key=lambda x: x[1], reverse=True)
(ind1, i) = (0, 0)
while i < n:
	if hor[i][1] == 0 and hor[i][2] == 10 ** 6:
		ans += 1
	while ind1 < m and topVer and (ver[ind1][1] > hor[i][0]):
		topVer.remove(ver[ind1][0])
		ind1 += 1
	if hor[i][1] == 0:
		ans += topVer.bisect_right(hor[i][2])
	else:
		ans += len(topVer) - topVer.bisect_left(hor[i][1])
	i += 1
hor.reverse()
ver.sort(key=lambda x: x[2])
(ind1, i) = (0, 0)
while i < n and botVer:
	while ind1 < m and botVer and (ver[ind1][2] < hor[i][0]):
		botVer.remove(ver[ind1][0])
		ind1 += 1
	if hor[i][1] == 0:
		ans += botVer.bisect_right(hor[i][2])
	else:
		ans += len(botVer) - botVer.bisect_left(hor[i][1])
	i += 1
out(ans)


import sys
input = sys.stdin.readline

class Bit:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i
(N, M) = map(int, input().split())
E = []
R = 1
for _ in range(N):
	(y, lx, rx) = map(int, input().split())
	E.append((3 * y + 1, (lx, rx)))
	if rx - lx == 10 ** 6:
		R += 1
for _ in range(M):
	(x, ly, ry) = map(int, input().split())
	E.append((3 * ly, x))
	E.append((3 * ry + 2, x))
	if ry - ly == 10 ** 6:
		R += 1
E.sort(key=lambda x: x[0])
bit = Bit(10 ** 6 + 1)
for (y, v) in E:
	if y % 3 == 1:
		R += bit.sum(v[1]) - bit.sum(v[0] - 1)
	elif y % 3 == 2:
		bit.add(v, -1)
	else:
		bit.add(v, 1)
print(R)


import sys
input = sys.stdin.readline

class Bit:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i
(n, m) = map(int, input().split())
e = []
r = 1
for i in range(n):
	(y, lx, rx) = map(int, input().split())
	e.append((3 * y + 1, (lx, rx)))
	if rx - lx == 10 ** 6:
		r += 1
for i in range(m):
	(x, ly, ry) = map(int, input().split())
	e.append((3 * ly, x))
	e.append((3 * ry + 2, x))
	if ry - ly == 10 ** 6:
		r += 1
e.sort(key=lambda x: x[0])
bit = Bit(10 ** 6 + 1)
for (y, x) in e:
	if y % 3 == 1:
		r += bit.sum(x[1]) - bit.sum(x[0] - 1)
	elif y % 3 == 0:
		bit.add(x, 1)
	else:
		bit.add(x, -1)
print(r)


import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
MaxLength = 1 << 20
FenwickTree = []
CurLen = MaxLength
while CurLen != 0:
	FenwickTree.append([0] * CurLen)
	CurLen //= 2
Depth = len(FenwickTree)

def addElem(n, index):
	for m in range(Depth):
		if index < len(FenwickTree[m]):
			FenwickTree[m][index] += n
		index //= 2

def firstNSum(n):
	nCpy = n
	summ = 0
	depthCur = 0
	while nCpy != 0:
		if nCpy % 2 != 0:
			summ += FenwickTree[depthCur][nCpy - 1]
		nCpy //= 2
		depthCur += 1
	return summ
(n, m) = map(int, input().split())
QueryList = []
ans = 0
for _ in range(n):
	(a, b, c) = map(int, input().split())
	if b == 0 and c == 10 ** 6:
		QueryList.append((0, 1, a))
		ans += 1
	elif b == 0:
		QueryList.append((0, 1, a))
		QueryList.append((c + 1, -1, a))
	elif c == 10 ** 6:
		QueryList.append((b, 1, a))
QueryList.sort()
LineList = []
for _ in range(m):
	(a, b, c) = map(int, input().split())
	LineList.append((a, b, c))
	if b == 0 and c == 10 ** 6:
		ans += 1
LineList.sort()
QueryIndex = 0
LineIndex = 0
while True:
	if LineIndex >= len(LineList):
		break
	if QueryIndex >= len(QueryList) or LineList[LineIndex][0] < QueryList[QueryIndex][0]:
		ans += firstNSum(LineList[LineIndex][2] + 1) - firstNSum(LineList[LineIndex][1])
		LineIndex += 1
	elif LineIndex >= len(LineList) or LineList[LineIndex][0] >= QueryList[QueryIndex][0]:
		addElem(QueryList[QueryIndex][1], QueryList[QueryIndex][2])
		QueryIndex += 1
	else:
		break
print(ans + 1)


import sys
from collections import defaultdict
input = sys.stdin.buffer.readline
(fw, n) = ([0] * 1000002, 1000001)

def fw_add(p, val):
	while p <= n:
		fw[p] += val
		p += p & -p

def fw_sum(p):
	sm = 0
	while p > 0:
		sm += fw[p]
		p -= p & -p
	return sm

def fw_rsum(p1, p2):
	return fw_sum(p2) - fw_sum(p1 - 1)
(N, M) = map(int, input().split())
fw_add(1, 1)
fw_add(1000001, 1)
(rmv, add) = (defaultdict(list), defaultdict(list))
for _ in range(N):
	(y, x1, x2) = map(int, input().split())
	(y, x1, x2) = (y + 1, x1 + 1, x2 + 1)
	if x1 == 1:
		fw_add(y, 1)
		rmv[x2].append(y)
	else:
		add[x1].append(y)
query = {}
for _ in range(M):
	(x, y1, y2) = map(int, input().split())
	(x, y1, y2) = (x + 1, y1 + 1, y2 + 1)
	query[x] = (y1, y2)
query[1000001] = (1, 1000001)
cc = 0
for p in range(1, 1000002):
	if p in add:
		for y in add[p]:
			fw_add(y, 1)
	if p in query:
		(y1, y2) = query[p]
		cc += fw_rsum(y1, y2) - 1
	if p in rmv:
		for y in rmv[p]:
			fw_add(y, -1)
print(cc - sum((len(u) for u in add.values())))


import sys
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

class BitSum:

	def __init__(self, n):
		self.n = n + 1
		self.table = [0] * self.n

	def add(self, i, x):
		i += 1
		while i < self.n:
			self.table[i] += x
			i += i & -i

	def sum(self, i):
		i += 1
		res = 0
		while i > 0:
			res += self.table[i]
			i -= i & -i
		return res
from heapq import *

def solve(ans):
	enc = {y: i for (i, y) in enumerate(sorted(yy))}
	yn = len(yy)
	bit = BitSum(yn)
	bit.add(yn - 1, 1)
	while hp:
		(x, t, y1, r) = heappop(hp)
		if t == 0:
			bit.add(enc[y1], 1)
			heappush(hp, (r, 2, y1, -1))
		if t == 1:
			if y1 == 0:
				ans += bit.sum(enc[r])
			else:
				ans += bit.sum(enc[mx] - 1) - bit.sum(enc[y1] - 1)
		if t == 2:
			bit.add(enc[y1], -1)
	print(ans)
mx = 10 ** 6
(n, m) = MI()
yy = set([0, mx])
hp = []
ans = 1
for _ in range(n):
	(y, l, r) = MI()
	if l == 0 and r == mx:
		ans += 1
	heappush(hp, (l, 0, y, r))
	yy.add(y)
for _ in range(m):
	(x, l, r) = MI()
	heappush(hp, (x, 1, l, r))
	yy.add(l)
	yy.add(r)
solve(ans)


class BIT:

	def __init__(self, n):
		self.BIT = [0] * (n + 1)
		self.num = n

	def query(self, idx):
		res_sum = 0
		while idx > 0:
			res_sum += self.BIT[idx]
			idx -= idx & -idx
		return res_sum

	def update(self, idx, x):
		while idx <= self.num:
			self.BIT[idx] += x
			idx += idx & -idx
		return
import sys
input = sys.stdin.buffer.readline
(n, m) = map(int, input().split())
hori = []
ver = []
X = set([0, 10 ** 6])
Y = set([0, 10 ** 6])
add = 0
for i in range(n):
	(y, lx, rx) = map(int, input().split())
	add += int(rx - lx == 10 ** 6)
	X.add(lx)
	X.add(rx)
	Y.add(y)
	hori.append((y, lx, rx))
for i in range(m):
	(x, ly, ry) = map(int, input().split())
	add += int(ry - ly == 10 ** 6)
	X.add(x)
	Y.add(ly)
	Y.add(ry)
	ver.append((x, ly, ry))
X = list(X)
Y = list(Y)
X.sort()
Y.sort()
compX = {i: e + 1 for (e, i) in enumerate(X)}
compY = {i: e + 1 for (e, i) in enumerate(Y)}
Xmax = len(X) + 1
Ymax = len(Y) + 1
for i in range(n):
	(y, lx, rx) = hori[i]
	hori[i] = (compY[y], compX[lx], compX[rx])
for i in range(m):
	(x, ly, ry) = ver[i]
	ver[i] = (compX[x], compY[ly], compY[ry])
minus = 0
query = []
allbit = BIT(Xmax)
all = 0
for i in range(m):
	(x, ly, ry) = ver[i]
	query.append((x, -200, ly))
	query.append((x, -100, ry))
	allbit.update(x, 1)
for i in range(n):
	(y, lx, rx) = hori[i]
	query.append((lx - 1, 20000, y))
	query.append((rx, 10000, y))
	all += allbit.query(rx) - allbit.query(lx - 1)
query.sort()
rbit = BIT(Ymax)
lbit = BIT(Ymax)
for (x, q, y) in query:
	if q == -100:
		rbit.update(y, 1)
	elif q == -200:
		lbit.update(y, 1)
	elif q == 20000:
		tmp = rbit.query(y - 1) + lbit.query(Ymax) - lbit.query(y)
		minus -= tmp
	else:
		tmp = rbit.query(y - 1) + lbit.query(Ymax) - lbit.query(y)
		minus += tmp
print(all + add - minus + 1)


import sys
input = sys.stdin.readline

class BIT:

	def __init__(self, n):
		self.n = n + 1
		self.BIT = [0] * self.n

	def add(self, i, x):
		idx = i
		while idx < self.n:
			self.BIT[idx] += x
			idx += idx & -idx

	def _sum(self, i):
		if i == -1:
			return -1
		ret = 0
		idx = i
		while idx > 0:
			ret += self.BIT[idx]
			idx -= idx & -idx
		return ret

	def sum(self, l, r):
		return self._sum(r) - self._sum(l - 1)

	def value(self, i):
		return self._sum(i) - self._sum(i - 1)
bound = 10 ** 6
(n, m) = map(int, input().split())
yoko_edges = [list(map(int, input().split())) for _ in range(n)]
yoko_edges = sorted(yoko_edges, reverse=True, key=lambda x: x[0])
ue_tate_edges = [[] for _ in range(bound + 1)]
sita_tate_edges = [[] for _ in range(bound + 1)]
tate_edges = BIT(bound)
tate_edges.add(bound, 1)
ans = 1
for _ in range(m):
	(x, l, r) = map(int, input().split())
	if l == 0 and r == bound:
		tate_edges.add(x, 1)
		ans += 1
	elif l == 0:
		sita_tate_edges[r].append(x)
	elif r == bound:
		ue_tate_edges[l].append(x)
		tate_edges.add(x, 1)
prev = bound - 1
for (y, l, r) in yoko_edges:
	while prev >= y:
		for x in sita_tate_edges[prev]:
			tate_edges.add(x, 1)
		for x in ue_tate_edges[prev + 1]:
			tate_edges.add(x, -1)
		prev -= 1
	ans += tate_edges.sum(l, r) - 1
print(ans)


import io
import os
from collections import Counter, defaultdict, deque

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

def solve(N, M, YLR, XBT):
	H = []
	H.append((0, (0, 10 ** 6)))
	H.append((10 ** 6, (0, 10 ** 6)))
	for (y, l, r) in YLR:
		H.append((y, (l, r)))
	H.sort(key=lambda ylr: ylr[1][0])
	V = []
	V.append((0, (0, 10 ** 6)))
	V.append((10 ** 6, (0, 10 ** 6)))
	for (x, b, t) in XBT:
		V.append((x, (b, t)))
	V.sort()
	straddling = SortedList()
	straddlingByY = SortedList()
	goodLeftByY = SortedList()
	j = 0
	ans = 0
	for (index, (x, (b, t))) in enumerate(V):
		while straddling and straddling[0][0] < x:
			(r, i) = straddling.pop(0)
			straddlingByY.remove(H[i][0])
		if index != 0:
			lo = straddlingByY.bisect_left(b)
			hi = straddlingByY.bisect_right(t)
			assert hi - lo > 0
			ans += hi - lo - 1
		while j < len(H) and H[j][1][0] <= x:
			goodLeftByY.add((H[j][0], j))
			j += 1
		lo = goodLeftByY.bisect_left((b, 0))
		hi = goodLeftByY.bisect_right((t, 10 ** 7))
		move = list((goodLeftByY[k] for k in range(lo, hi)))
		for tup in move:
			(y, i) = tup
			(y, (l, r)) = H[i]
			assert b <= y <= t
			assert l <= x
			goodLeftByY.remove(tup)
			straddling.add((r, i))
			straddlingByY.add(y)
	return ans
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(N, M) = [int(x) for x in input().split()]
YLR = ((int(x) for x in input().split()) for i in range(N))
XBT = ((int(x) for x in input().split()) for i in range(M))
ans = solve(N, M, YLR, XBT)
print(ans)


import sys
input = sys.stdin.readline

class Bit:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i
(x, y) = list(map(int, input().split()))
ans = 1
fenwick = Bit(10 ** 6 + 1)
events = []
for _ in range(x):
	(a, b, c) = list(map(int, input().split()))
	if b == 0 and c == 10 ** 6:
		ans += 1
	events.append((a, 1, b, c))
for _ in range(y):
	(a, b, c) = list(map(int, input().split()))
	if b == 0 and c == 10 ** 6:
		ans += 1
	events.append((b, 0, a, c))
	events.append((c, 2, a, c))
events.sort()
for e in events:
	(h, b, c, d) = e
	if b == 1:
		ans += fenwick.sum(d) - fenwick.sum(c - 1)
	if b == 0:
		fenwick.add(c, 1)
	if b == 2:
		fenwick.add(c, -1)
print(ans)