반물질 비

산성비는 들어봤어도 반물질 비는 들어봤는가? 반물질 비는 너무나 강력해서 다른 물체와 닿는 순간 자신과 그 물체를 즉시 분해한다. SpaceFleet 연구원인 Kayla의 일은 특이한 행성의 기상 데이터를 수집하는 것이다. 이번 임무는 반물질 강우량을 관측하는 것이다.

행성 대기에 센서가 설치되어 있고, 곧 반물질 비가 내릴 예정이다. 이런! Kayla는 하나의 2D 단면을 관측한다. 각 센서는 하나의 수평 막대이거나 하나의 점이다. 하나 이상의 반물질 방울이 하나의 센서에 떨어지면, 그 방울들과 센서는 동시에 분해된다. 즉, 사라진다. 다른 모든 방울은 센서가 있던 자리를 지나 계속 떨어진다.

Kayla는 모든 반물질 빗방울이 떨어지기 시작하는 순간 직전에 그것들을 본다. 모든 방울은 정확히 같은 속도로 떨어진다.

각 방울에 대해, Kayla는 그것이 분해될지, 그리고 어디서 분해될지 알고 싶어한다. 이 까다로운 작업을 도와주자!

첫 번째 예시의 그림. 수직선은 방울과 그것이 맞는 센서를 연결한다. 수직선이 없는 방울은 어떤 센서와도 만나지 않는다.

입력의 첫 번째 줄에는 두 정수 $D$ ($1 \leq D \leq 100\,000$)와 $S$ ($1 \leq S \leq 100\,000$)가 주어진다. $D$는 반물질 방울의 수이고, $S$는 센서의 수이다.

다음 $D$개의 줄은 방울을 순서대로 설명한다. 각 줄에는 두 정수 $x$ ($1 \leq x \leq 10^9$)와 $y$ ($1 \leq y \leq 10^9$)가 주어진다. $x$는 방울의 $x$좌표이고, $y$는 방울의 $y$좌표이다.

다음 $S$개의 줄은 센서를 설명한다. 각 줄에는 세 정수 $x\_1$, $x\_2$ ($1 \leq x\_1 \leq x\_2 \leq 10^9$)와 $y$ ($1 \leq y \leq 10^9$)가 주어진다. $x\_1$과 $x\_2$는 센서의 가장 왼쪽과 가장 오른쪽 $x$좌표이고, $y$는 센서의 $y$좌표이다.

어떤 두 방울도 같은 위치에서 시작하지 않고, 어떤 방울도 센서 위에서 시작하지 않으며, 어떤 두 센서도 (한 점에서조차) 닿지 않음이 보장된다.

각 방울에 대해, 순서대로, 그것이 분해될 $y$좌표를 나타내는 하나의 수를 출력한다. 방울이 분해되지 않으면 대신 $0$을 출력한다. 이 값들은 각각 별도의 줄에 나타나야 한다.