새 보금자리

우푸 거리는 완전히 곧게 뻗은 거리다. 이 거리는 1차원 수직선으로 나타낼 수 있어서, 거리에 놓인 건물의 위치는 수 하나로 표현한다. 시간 여행자 샤오밍은 이 거리에 문을 열었던 가게, 지금 열려 있는 가게, 앞으로 열 가게를 모두 알고 있다. 가게는 $k$가지 종류로 나뉘고 모두 $n$개다. $i$번 가게는 네 정수 $x_i$, $t_i$, $a_i$, $b_i$로 주어지며, 각각 가게의 위치, 가게의 종류, 영업을 시작하는 연도, 영업을 끝내는 연도다. $a_i \le y \le b_i$이면 $i$번 가게는 $y$년에 영업한다.

샤오밍은 우푸 거리에서 살 연도와 위치를 고르려 하고, 후보를 위치와 연도의 쌍 $q$개로 좁혔다. $i$번 쌍은 두 정수 $l_i$, $y_i$로 주어진다. 샤오밍은 각 쌍을 불편도로 평가한다. 불편도는 그 쌍에서 가장 가기 어려운 종류의 접근 불편함이다. 어떤 쌍에서 종류 $t$의 접근 불편함은 그 위치에서 그 연도에 영업하는 가장 가까운 $t$종류 가게까지의 거리다. 따라서 불편도는 $k$가지 종류에 대한 이 거리의 최댓값이다. 어떤 해에는 우푸 거리에 $k$가지 종류가 다 있지는 않다. 이런 쌍의 불편도는 $-1$로 정한다.

각 쌍의 불편도를 구하라.

첫째 줄에 세 정수 $n$, $k$, $q$가 주어진다. 각각 가게의 수, 종류의 수, 질의의 수다 ($1 \le n, q \le 3 \times 10^5$, $1 \le k \le n$).

다음 $n$개 줄에는 가게 하나를 나타내는 네 정수 $x_i$, $t_i$, $a_i$, $b_i$가 주어진다 ($1 \le x_i, a_i, b_i \le 10^8$, $1 \le t_i \le k$, $a_i \le b_i$).

다음 $q$개 줄에는 질의 하나를 나타내는 두 정수 $l_i$, $y_i$가 주어진다 ($1 \le l_i, y_i \le 10^8$).

정수 $q$개를 입력에 주어진 질의 순서대로 한 줄에 하나씩 출력한다. $i$번째 값은 $i$번째 질의의 불편도다.

첫 번째 예제에는 가게 4개, 종류 2가지, 질의 4개가 있다.

• 첫 번째 질의: 샤오밍은 3년에 위치 5에 산다. 이 해에는 1번 가게와 2번 가게가 영업하고, 1번까지 거리는 2, 2번까지 거리는 4이므로 답은 4다.
• 두 번째 질의: 6년에 위치 5에 산다. 1번 가게와 3번 가게가 영업하고 둘 다 거리가 2이므로 답은 2다.
• 세 번째 질의: 9년에 위치 5에 산다. 1번 가게와 4번 가게가 영업하는데 둘 다 1종류라서 2종류 가게가 하나도 없다. 답은 $-1$이다.
• 네 번째 질의: 상황이 같으므로 답은 $-1$이다.

두 번째 예제에는 가게 2개, 종류 1가지, 질의 3개가 있다. 두 가게 모두 위치 1에 있고 질의도 모두 위치 1을 묻는다. 앞의 두 질의에서는 적어도 한 가게가 영업하므로 답이 0이고, 세 번째 질의에서는 두 가게가 모두 닫혀 있으므로 답이 $-1$이다.

세 번째 예제에는 가게 1개와 질의 1개가 있고, 두 위치 사이의 거리는 99999999다.