Warships

Hongjun is a proud sailor in the navy. Today he runs a live-fire drill that simulates a battle against the enemy from aboard a warship.

The battlefield is an $n \times n$ grid. The bottom-left point has coordinates $(1, 1)$ and the top-right point has coordinates $(n, n)$. The enemy fleet consists of $k$ warships. Each warship $i$ is a line segment of positive length connecting its two endpoints $(x_i, y_i)$ and $(x'_i, y'_i)$, and it has weight $w_i$.

To destroy the warships, Hongjun fires a laser cannon a total of $l$ times. Each shot is fired either vertically or horizontally.

• A vertical shot is the segment connecting $(a, 1)$ and $(a, n)$; it destroys every warship that touches this segment (endpoints included).
• A horizontal shot is the segment connecting $(1, a)$ and $(n, a)$; it destroys every warship that touches this segment (endpoints included).

After each shot, Hongjun must report the weight of the heaviest warship destroyed by that shot. A warship that has already been destroyed cannot be destroyed again by a later shot.

Given every warship's position and the shots in order, for each shot output the weight of the heaviest warship it destroys. If a shot destroys no warship, report $0$.

The first line contains the number of test cases $T$.

For each test case, the first line contains the grid size $n$, the number of warships $k$, and the number of shots $l$. ($1 \le n \le 10^9$, $1 \le k, l \le 10^5$)

Each of the next $k$ lines contains five integers $x$, $y$, $x'$, $y'$, $w$, describing a warship with endpoints $(x, y)$ and $(x', y')$ ($1 \le x, y, x', y' \le n$) and weight $w$ ($1 \le w \le 10^6$). Every warship has positive length.

Each of the next $l$ lines contains two integers $a$ and $b$. ($1 \le a \le n$, $b \in {0, 1}$) If $b = 0$, the shot is the horizontal segment from $(1, a)$ to $(n, a)$; if $b = 1$, it is the vertical segment from $(a, 1)$ to $(a, n)$.

For each test case, print $l$ lines. On the $i$-th line, print the weight of the heaviest warship destroyed by the $i$-th shot, or $0$ if that shot destroys no warship.