레이저

이차원 평면에 $x$축과 평행한 선분, 즉, 수평선분이 $N$ 개 놓여있다. $i$ 번째 선분의 양 끝점은 $(L_i, H_i)$와 $(R_i, H_i)$이다.

또한, 레이저 발사기 $M$ 개가 있다. 편의상 레이저 발사기에 $1$번부터 $M$번까지 번호가 매겨져 있다. $j$번 레이저 발사기는 $(X_j, Y_j)$에 놓여 있다. $j$번 레이저 발사기에서 발사된 레이저는 $y$축에 평행하게 $y$좌표가 증가하는 수직 방향으로 뻗어나가며, $P_j$ 개의 선분을 뚫고 지나갈 수 있다. $j$번 레이저 발사기에서 발사된 레이저가 선분을 $P_j$ 번 뚫고 지나간 이후 선분을 만나면 더 이상 뻗어나가지 않고 그 자리에서 소멸한다. 레이저가 뚫고 지나간 선분은 그 즉시 파괴되어 없어진다.

레이저 발사기가 번호 순서대로 레이저를 발사할 때, 각 레이저가 뻗어나간 거리를 구하는 프로그램을 작성하라. 어떤 레이저는 무한히 뻗어나갈 수 있음에 유의하라.

입력 형식

첫 줄에 수평선분의 개수를 나타내는 정수 $N$과 레이저 발사기의 개수를 나타내는 정수 $M$이 공백으로 구분되어 주어진다. ($1 \le N, M \le 50\,000$)

이어지는 $N$ 개의 줄의 $i$ 번째 줄에는 $i$ 번째 선분의 정보를 나타내는 세 정수 $L_i$, $R_i$, $H_i$가 공백으로 구분되어 주어진다. ($-1\,000\,000\,000 \le L_i < R_i \le 1\,000\,000\,000$; $-1\,000\,000\,000 \le H_{i} \le 1\,000\,000\,000$)

이어지는 $M$ 개의 줄의 $j$ 번째 줄에는 $j$번 레이저 발사기의 정보를 나타내는 세 정수 $X_j$, $Y_j$, $P_j$가 공백으로 구분되어 주어진다. ($-1\,000\,000\,000 \le X_i, Y_i \le 1\,000\,000\,000$; $0 \le P_{i} \le N$)

주어지는 모든 $x$ 좌표는 서로 다르고, 주어지는 모든 $y$좌표도 서로 다르다.

출력 형식

$M$ 개의 줄에 걸쳐 답을 출력한다. $j$ 번째 줄에 $j$번 레이저 발사기에서 발사된 레이저가 뻗어나간 거리를 출력한다. 만약, 레이저가 무한히 뻗어나가면 -1을 출력한다.

예제

5 3
4 11 7
8 12 8
6 13 3
1 7 4
2 10 9
5 2 2
9 5 2
3 6 1

7
-1
-1

예제 설명

$1$번 레이저 발사기에서 레이저가 발사된 이후의 순간이다. 이 레이저는 선분 $2$ 개를 뚫고 지나갈 수 있다.

처음 발사된 레이저에 의해 선분 $2$ 개가 파괴되어 없어지고, $2$번 레이저 발사기에서 레이저가 발사된 이후의 순간이다. 이 레이저는 선분 $2$ 개를 뚫고 지나갈 수 있으며, 이후 무한히 뻗어나간다.

$3$번 레이저 발사기에서 레이저가 발사된 이후의 순간이다. 이 레이저는 선분 $1$ 개를 뚫고 지나갈 수 있으며, 이후 무한히 뻗어나간다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설