통나무 \(N\)개가 가로(수평) 방향으로 연못에 떠 있다. 개구리는 한 통나무 \(A\)에서 다른 통나무 \(B\)로 정확히 수직 방향으로 점프할 수 있다. 단, 점프할 때 다른 통나무 위를(끝 점 포함) 지나면 안 된다.

예를 들어 <그림 1>에서 1번 통나무에서 2번 통나무로 점선을 따라 개구리가 점프하는 것이 가능하다. 1번 통나무에서 2번 통나무로 점프한 후 다시 3번 통나무로 점프하면 1번 통나무에서 3번 통나무로 이동하는 것이 가능하다. (통나무 위에서 걸어서 움직이는 것은 언제든 가능하다.)

<그림 1>의 예: 1번 통나무는 \(x\)구간 \([1,5]\), 높이 \(2\). 2번 통나무는 \(x\)구간 \([3,7]\), 높이 \(4\). 3번 통나무는 \(x\)구간 \([7,9]\), 높이 \(1\). 4번 통나무는 \(x\)구간 \([10,13]\), 높이 \(4\).

통나무들의 위치를 입력받아, 질문으로 주어진 통나무들의 쌍에 대해서 개구리가 한 통나무에서 다른 통나무로 한 번 이상의 점프로 이동이 가능한지 판단하는 프로그램을 작성하라.

※ 이 문제의 채점 데이터는 공개된 공식 데이터가 없어 재구성한 것입니다.

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 통나무의 개수 \(N\)과 질문의 개수 \(Q\)가 주어진다. 다음 \(N\)개의 줄에 각 통나무의 세 정수 좌표 \(x_1\), \(x_2\), \(y\)가 주어진다. 주어진 통나무는 두 점 \((x_1, y)\)와 \((x_2, y)\)를 잇는 형태이다. (\(x_1 < x_2\)) 모든 좌표는 \(0\) 이상 \(10^9\) 이하이다. 통나무들은 주어진 순서대로 \(1\)번부터 번호가 붙어 있다. 서로 다른 두 통나무는 (끝점에서도) 만나지 않는다.

다음 \(Q\)개의 줄에 서로 다른 두 통나무의 번호가 주어진다. (\(1 \le N \le 100{,}000\), \(1 \le Q \le 100{,}000\))

표준 출력으로 \(Q\)개의 줄을 출력한다. 각 줄에는 주어진 순서대로 질문에 대한 대답이 출력되어야 한다. 질문에 주어진 두 통나무에 대해서 개구리가 한 통나무에서 다른 통나무로 한 번 이상의 점프로 이동이 가능한 경우 대답은 \(1\), 그렇지 않은 경우 대답은 \(0\)이다.

생성자가 기록되지 않았습니다.

출처 올림피아드 > 한국정보올림피아드 > KOI 2019 > 2차 대회 > 중등부 2번