I. Flappy Deer
time limit per test
6 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Noko-tan is playing the hit game "Flappy Deer". In this game, Noko-tan controls a flying deer who moves in an infinite 2-D grid. The deer is initially located at some cell. Every second, the deer will move to the right by a single unit (increase $$$x$$$ coordinate by one), and Noko-tan can choose whether to move the deer up by one unit (increase $$$y$$$ coordinate by one), keep the deer's current height, or move the deer down by one unit (decrease $$$y$$$ coordinate by one). There are also $$$N$$$ full water bottles that Noko-tan is deathly afraid of. Thus, if her flying deer ever shares a cell with a water bottle, the game will immediately end. The $$$i$$$-th water bottle is a rectangle occupying the cells in between $$$(x_i, a_i)$$$ and $$$(x_i, b_i)$$$. Finally, to make things interesting, there are also deer crackers floating around. The $$$j$$$-th is located at cell $$$(x_j, y_j)$$$. Noko-tan collects a deer cracker if her flying deer occupies the same cell as that deer cracker. Since Noko-tan has antlers for brains, she doesn't know how to play in order to collect the maximum number of deer crackers. Thus, she asks you to help her find this value for $$$Q$$$ starting positions. Note that Noko-tan encountering a water bottle ends the game, but does not reset the number of crackers she has collected. Also, the grid is infinite, so there is no bounds on Noko-tan's maximum $$$x$$$ or $$$y$$$ coordinates.

Input

The first line contains two integers $$$N$$$, $$$M$$$, and $$$Q$$$ ($$$1 \le N, M, Q \le 10^5$$$).

The next $$$N$$$ lines will contain three integers $$$x_i$$$, $$$a_i$$$, and $$$b_i$$$ ($$$0 \le x_i \le 10^8$$$, $$$-10^8 \le a_i \le b_i \le 10^8$$$) — the locations of the water bottles.

The next $$$M$$$ lines will contain two integers $$$x_j$$$ and $$$y_j$$$ ($$$0 \le x_j \le 10^8$$$, $$$-10^8 \le y_j \le 10^8$$$) — the locations of the deer crackers.

The next $$$Q$$$ lines will contain two integers $$$x_k$$$ and $$$y_k$$$ ($$$0 \le x_k \le 10^8$$$, $$$-10^8 \le y_k \le 10^8$$$) — the starting positions.

—

There are $$$20$$$ tests, not including samples. Each test is worth $$$\frac{100}{20}=5$$$ points.

For tests $$$1$$$ — $$$2$$$, it is guaranteed that all given coordinates are between $$$0$$$ and $$$1000$$$.

For tests $$$3$$$ — $$$4$$$, it is guaranteed that all given coordinates are between $$$0$$$ and $$$10000$$$.

For tests $$$5$$$ — $$$10$$$, it is guaranteed that all given coordinates are between $$$0$$$ and $$$100000$$$ and $$$Q = 1$$$.

For tests $$$11$$$ — $$$15$$$ it is guaranteed that all given coordinates are between $$$0$$$ and $$$100000$$$.

For tests $$$16$$$ — $$$20$$$ there are no additional constraints.

Output

For each starting position, output a single integer — the maximum number of deer crackers Noko-tan can collect.

Example
Input
3 78 2
8 7 9
24 12 14
24 7 9
5 7
6 7
7 7
7 8
7 9
7 10
5 10
5 11
5 12
5 13
6 13
7 13
9 7
9 8
9 9
9 10
9 11
9 12
9 13
10 10
11 10
12 7
12 8
12 9
12 10
12 11
12 12
12 13
14 7
15 7
16 7
17 7
15 8
15 9
15 10
15 11
15 12
16 8
16 9
16 10
16 11
16 12
14 13
15 13
16 13
17 13
19 7
19 8
19 9
19 10
19 11
19 12
19 13
20 10
21 11
22 12
23 13
21 9
22 8
23 7
25 7
25 8
25 9
25 10
25 11
25 12
25 13
26 13
27 13
26 10
27 10
28 7
28 8
28 9
28 10
28 11
28 12
28 13
0 0
0 10
Output
15
19
Note

Image depicting one of Noko-tan's optimal paths starting from $$$(0, 0)$$$ in the sample test:

—

Problem Idea: oursaco

Problem Preparation: oursaco

Occurrences: Advanced I