Space Gophers

Space Gophers live on a strange, cube-shaped asteroid whose every side has length exactly $N = 10^6$. The geographers have divided the asteroid into $N \times N \times N$ microcubes and introduced a standard Cartesian coordinate system, so every microcube has three coordinates $(x, y, z)$.

The Gophers' main occupation, and also their favorite pastime, is tunnel digging. Many tunnels have been dug in the asteroid. Each tunnel starts at one of the asteroid's outer walls and is a straight line of removed microcubes, perpendicular to that wall, running all the way through to the opposite side. Today is a grand festival, though, and all digging is forbidden for now. Any Gopher who wants to visit friends must move through empty space only.

Navigation is hard for the Gophers, so they need your help. You are given a list of pairs of starting and ending positions. For each pair, determine whether the end can be reached from the start by moving only through empty microcubes. The Gophers move only through space they have dug, and they never leave the initial cube. This is probably some kind of agoraphobia.

The first line contains the number of test cases $z$ ($1 \le z \le 6$). Each test case is described as follows.

The first line of a test case contains a positive integer $n$ ($n \le 300\,000$), the number of tunnels. The next $n$ lines describe the tunnels. Each line contains a triple of integers of one of the forms $(x, y, -1)$, $(x, -1, z)$, or $(-1, y, z)$, where $1 \le x, y, z \le 10^6$.

The triple $(x, y, -1)$ means that a tunnel removes all microcubes $(x, y, t)$ for every integer $t$. Similarly, $(x, -1, z)$ removes all $(x, t, z)$, and $(-1, y, z)$ removes all $(t, y, z)$.

The next line contains the number of queries $q$ ($1 \le q \le 500\,000$). Each of the following $q$ lines contains six integers $(x_1, y_1, z_1, x_2, y_2, z_2)$, each between 1 and $10^6$. Each query asks for a route from the cube $(x_1, y_1, z_1)$ to the cube $(x_2, y_2, z_2)$ that visits only empty cubes and moves between adjacent cubes. Two cubes are adjacent if they share a face. All starting and ending positions are guaranteed to be empty.

For each test case, output the answers to all of its queries, one per line. Output "YES" if a route exists and "NO" if it does not.