In a galaxy far away, there is a constant battle between the republic and the droid army. The droid army decided to launch their final attack on the republic. They have N space-fighters. 

Initially the $i^{th}$ fighter is located at (x_{i}, y_{i}). All of the space-fighters move with constant velocity V units/sec in the positive X direction. 
i.e., fighter at (x_{i}, y_{i}) moves to (x_{i}+V, y_{i}) in 1 second. 
The $ i^{th} $ space-fighter broadcasts enemy information at a frequency f_{i}.

The republic is not scared of the artificially intelligent droid force as they have Yoda. Yoda has a special power, at any time T he can choose a region of the droid army and block one specific frequency F. This power has one constraint; it can be applied only in the form of a two sided unbounded axis parallel rectangular box open towards the both the directions across X axis (refer image below for clarity). If a frequency (F) is blocked all the space-fighters in the region having the frequency F can’t communicate.

Given the initial positions of the space-fighters, and their velocity, you are to answer queries of the following form:

YU YD T

where YU, YD are the bounds on y-axis inside which YODA can block a frequency at time T. 
In the region described by the query, after a time T seconds from the start, if Yoda can chose one frequency (F) he wishes to, what is the maximum number of communications he can block?

Input Format 

Each test case is described as follows; the first line contains 3 space separated integers N - the number of space-fighters, Q - the number of queries you have to answer, and V - the velocity of the space-fighters separated by a single space. 

N lines follow, each containing 3 space separated integers x_{i}, y_{i}, and f_{i}, denoting the x co-ordinate, y co-ordinate and the frequency at which the $ i^{th} $ ship broadcasts respectively. Each of the next Q lines contain 3 space separated integers representing YU, YD, T respectively. Refer the figure for more clarity

Note: Points on the boundaries should be counted as well.

Output Format 

For each query you are to output a single integer denoting the result.

Constraints 

1 <= N <= 50000

1 <= Q <= 30000

1 <= V <= 10000

 $-10^{9}  $<= x_{i} <=  $10^{9} $

 $-10^{9} $ <= y_{i} <=  $10^{9} $

1 <= f_{i} <=  $10^{9} $

 $-10^{9} $ <= YU <= $ 10^{9} $

 $-10^{9}  $<= YD <=  $10^{9} $

1 <= T <= 10000

YU >= YD

Sample Input

5 5 82
-4 1 4
-3 -2 2
-3 5 1
0 -5 2
1 -1 2
1 -1 57
-2 -5 11
5 -5 40
-1 -5 16
5 -1 93

Sample Output

1
2
3
3
1

Explanation
Consider the points ships in the Y-range 1 to -1, they are the (-4, 1) and (1, -1), and both operate on different frequencies, hence the most times a frequency is repeated is once.

Difficulty: HARD
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


import bisect
from itertools import chain
from collections import defaultdict
import math
import sys

def round_down(i, n):
	return i - i % n

def round_up(i, n):
	rem = i % n
	if rem == 0:
		return i
	return i + (n - rem)
(N, Q, V) = map(int, input().split())
ships = [list(map(int, input().split()))[1:3] for _ in range(N)]
ships.sort(key=lambda p: p[0])
block_size = int(math.sqrt(N))
extra_ships = block_size - (N - 1) % block_size
for i in range(1, extra_ships + 1):
	ships.append([1000000000 + i, -i])
N += extra_ships
(num_of_freqs, input_freqs) = (0, {})
freqs_pos = [[]]
freqs_cnt = [0] * N
for i in range(N):
	(y, f_raw) = ships[i]
	if not f_raw in input_freqs:
		num_of_freqs += 1
		L = [1, num_of_freqs]
		input_freqs[f_raw] = L
	else:
		L = input_freqs[f_raw]
		L[0] += 1
	(n, f) = L
	if f == len(freqs_pos):
		freqs_pos.append([])
	freqs_pos[f].append(i)
	freqs_cnt[i] = n
	ships[i][1] = f
num_of_blocks = (N - 1) // block_size
stat = [[0] * (num_of_blocks + 1) for _ in range(num_of_blocks + 1)]
for i_min in range(0, N - block_size, block_size):
	d = defaultdict(int)
	d_max = 0
	i_prev = i_min
	for i_max in range(i_min + block_size, N, block_size):
		for i in range(i_prev, i_max):
			f = ships[i][1]
			d[f] += 1
			d_max = max(d_max, d[f])
		i_prev = i_max
		stat[i_min // block_size][i_max // block_size] = d_max
ships_y = [s[0] for s in ships]
for qid in range(Q):
	(y_max, y_min, t) = map(int, input().split())
	i_min = bisect.bisect_left(ships_y, y_min)
	i_max = bisect.bisect(ships_y, y_max)
	if i_min == i_max:
		print(0)
		continue
	idx_block_min = round_up(i_min, block_size) // block_size
	idx_block_max = round_down(i_max, block_size) // block_size
	prefix_end = idx_block_min * block_size
	suffix_start = idx_block_max * block_size
	best = 0
	if idx_block_min >= idx_block_max:
		prefix_end = i_max
		suffix_start = i_max
	else:
		best = stat[idx_block_min][idx_block_max]
	seen = set([])
	for i in range(i_min, prefix_end):
		f = ships[i][1]
		if f in seen:
			continue
		seen.add(f)
		n = freqs_cnt[i]
		while n + best <= len(freqs_pos[f]) and freqs_pos[f][n + best - 1] < i_max:
			best += 1
	seen = set([])
	for i in range(i_max - 1, suffix_start - 1, -1):
		f = ships[i][1]
		if f in seen:
			continue
		seen.add(f)
		n = freqs_cnt[i]
		while n - best >= 1 and freqs_pos[f][n - best - 1] >= i_min:
			best += 1
	print(best)


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


import os
import sys
import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


from bisect import bisect_left, bisect_right
from collections import defaultdict
(n, q, _) = map(int, input().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, input().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, input().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


import math
import os
import random
import re
import sys
from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


import math
import os
import random
import re
import sys
import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


import math
import os
import random
import re
import sys
from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')


from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
(n, q, _) = map(int, sys.stdin.readline().split())
fighters = defaultdict(list)
res = []
for _ in range(n):
	(_, y, f) = map(int, sys.stdin.readline().split())
	fighters[f].append(y)
fighters = sorted(fighters.values(), key=len, reverse=True)
for i in fighters:
	i.sort()
for _ in range(q):
	(yu, yd, _) = map(int, sys.stdin.readline().split())
	val = 0
	for i in fighters:
		length = len(i)
		if length <= val:
			break
		start = bisect_left(i, yd)
		if length - start <= val or i[start] > yu:
			continue
		val = max(val, bisect_right(i, yu) - start)
	res.append(val)
print('\n'.join(map(str, res)))


import bisect
from collections import defaultdict
(N, Q, _) = map(int, input().split())
a = defaultdict(list)
y = list()
for _ in range(N):
	(_, y_, freq) = map(int, input().split())
	a[freq].append(y_)
	y.append(y_)
a = {freq: sorted(y) for (freq, y) in a.items() if len(y) > 1}
y = sorted(y)
res = []
for _ in range(Q):
	(y_max, y_min, T) = map(int, input().split())
	lres = 0
	index_start = bisect.bisect_left(y, y_min)
	if y[index_start] <= y_max:
		lres = 1
		for freq in a:
			index_start = bisect.bisect_left(a[freq], y_min)
			index_stop = bisect.bisect_right(a[freq], y_max)
			lres = max(lres, index_stop - index_start)
	res.append(lres)
print(*res, sep='\n')