우주 고퍼

우주 고퍼들은 한 변의 길이가 정확히 $N = 10^6$인 정육면체 모양의 기묘한 소행성에 살고 있다. 지리학자들은 이 소행성을 $N \times N \times N$개의 미세 정육면체로 나누고, 각 미세 정육면체를 $(x, y, z)$ 세 좌표로 나타내는 직교 좌표계를 정했다.

고퍼들의 주된 일이자 가장 좋아하는 취미는 땅굴 파기다. 소행성에는 많은 땅굴이 뚫려 있다. 각 땅굴은 소행성의 바깥쪽 벽 중 한 곳에서 시작해, 그 벽에 수직인 직선을 따라 미세 정육면체를 제거하며 반대편 벽까지 이어진다. 하지만 오늘은 큰 축제날이라 땅파기가 전면 금지되었다. 친구를 방문하려는 고퍼는 빈 공간으로만 이동해야 한다.

고퍼들에게 길 찾기는 어려우므로 도움이 필요하다. 출발 위치와 도착 위치의 쌍들이 주어지면, 빈 미세 정육면체만 지나서 출발 위치에서 도착 위치로 갈 수 있는지 판단하라. 고퍼는 파낸 공간으로만 움직이며, 처음 정육면체 바깥으로는 나가지 않는다. 이는 일종의 광장공포증일지도 모른다.

첫 줄에 테스트 케이스의 수 $z$ ($1 \le z \le 6$)가 주어진다. 각 테스트 케이스는 다음과 같이 구성된다.

테스트 케이스의 첫 줄에는 땅굴의 개수 $n$ ($n \le 300\,000$)이 양의 정수로 주어진다. 이어서 $n$개의 줄에 땅굴이 하나씩 주어진다. 각 줄은 $(x, y, -1)$, $(x, -1, z)$, $(-1, y, z)$ 중 하나의 형태를 띤 정수 세 개이며, $1 \le x, y, z \le 10^6$을 만족한다.

$(x, y, -1)$은 모든 정수 $t$에 대해 $(x, y, t)$ 미세 정육면체를 제거한 땅굴을 뜻한다. 마찬가지로 $(x, -1, z)$는 모든 $(x, t, z)$를, $(-1, y, z)$는 모든 $(t, y, z)$를 제거한 땅굴을 뜻한다.

다음 줄에는 질문의 수 $q$ ($1 \le q \le 500\,000$)가 주어진다. 이어서 $q$개의 줄에 $1$ 이상 $10^6$ 이하의 정수 여섯 개 $(x_1, y_1, z_1, x_2, y_2, z_2)$가 주어진다. 각 질문은 $(x_1, y_1, z_1)$ 칸에서 $(x_2, y_2, z_2)$ 칸까지, 빈 칸만 거치고 인접한 칸끼리 이동하는 경로가 있는지를 묻는다. 두 칸은 면을 공유할 때 인접한다. 모든 출발 위치와 도착 위치는 빈 칸임이 보장된다.

각 테스트 케이스마다 그 질문들에 대한 답을 한 줄에 하나씩 출력한다. 경로가 있으면 "YES", 없으면 "NO"를 출력한다.