전함

홍준이는 대한민국의 자랑스러운 해군이다. 오늘은 전함을 타고 적과 싸우는 상황을 가정한 실전 연습을 한다.

전장은 $n \times n$ 크기의 격자이다. 가장 왼쪽 아래 점의 좌표는 $(1, 1)$, 가장 오른쪽 위 점의 좌표는 $(n, n)$이다. 적 함대는 전함 $k$개로 이루어져 있다. 각 전함 $i$는 두 끝점 $(x_i, y_i)$, $(x'_i, y'_i)$를 잇는 길이가 $0$보다 큰 선분이며, 무게는 $w_i$이다.

홍준이는 전함을 부수기 위해 레이저 대포를 모두 $l$번 발사한다. 대포는 수직 또는 수평으로 발사할 수 있다.

• 수직 발사: 레이저는 $(a, 1)$과 $(a, n)$을 잇는 선분이며, 이 선분과 만나는(끝점 포함) 전함을 모두 파괴한다.
• 수평 발사: 레이저는 $(1, a)$와 $(n, a)$를 잇는 선분이며, 이 선분과 만나는(끝점 포함) 전함을 모두 파괴한다.

레이저를 발사할 때마다, 그 발사로 파괴된 전함 중 가장 무거운 전함의 무게를 보고해야 한다. 이미 파괴된 전함은 이후 발사에서 다시 파괴되지 않는다.

모든 전함의 위치와 발사한 레이저의 정보가 순서대로 주어질 때, 각 발사마다 파괴된 전함 중 가장 무거운 무게를 구하는 프로그램을 작성하시오. 파괴된 전함이 없으면 $0$을 보고한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에는 격자의 크기 $n$, 전함의 수 $k$, 대포 발사 횟수 $l$이 주어진다. ($1 \le n \le 10^9$, $1 \le k, l \le 10^5$)

이어지는 $k$개의 줄에는 각 전함을 나타내는 다섯 정수 $x$, $y$, $x'$, $y'$, $w$가 주어진다. 이는 전함의 두 끝점 $(x, y)$, $(x', y')$ ($1 \le x, y, x', y' \le n$)와 무게 $w$ ($1 \le w \le 10^6$)를 뜻한다. 각 전함의 길이는 항상 $0$보다 크다.

그 다음 $l$개의 줄에는 각 발사를 나타내는 두 정수 $a$와 $b$가 주어진다. ($1 \le a \le n$, $b \in \{0, 1\}$) $b = 0$이면 $(1, a)$와 $(n, a)$를 잇는 수평 발사, $b = 1$이면 $(a, 1)$과 $(a, n)$을 잇는 수직 발사이다.

각 테스트 케이스마다 $l$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 레이저 발사로 파괴된 전함 중 가장 무거운 전함의 무게를 출력한다. 파괴된 전함이 없으면 $0$을 출력한다.