Color Mixing

A hardware store has a machine that mixes red, green, and blue (called the primary colors from here on) to make various shades. Each shade the machine can mix is given by an RGB code, which shows how much of each primary color it uses. Each code is three 16-bit integers. Customers ask for specific shades, also given as RGB codes. The machine may not be able to make the exact shade requested, so it picks the closest one it can make. "Closeness" is measured by the 3D Manhattan distance in RGB space. For example, the distance between the shades "100 50 0" and "20 25 10" is the sum of the differences in each primary color, $|100-20|+|50-25|+|0-10|=115$. On some days the machine runs out of one of the primary colors (red, green, or blue). In that case, customers only request shades that do not need that primary color. The machine was built so that its shades are spread evenly across RGB space, so you can assume the possible shades are roughly random and equally likely. All shades the machine can make are different from each other, but customer requests may repeat.

The first line contains the number of shades the machine can make $1 \le N \le 100\,000$ and the number of requests $1 \le Q \le 100\,000$. Each of the next $N + Q$ lines contains three integers from 0 to 65535, the RGB code of one color. The first $N$ lines are the codes of the shades the machine can mix. The last $Q$ lines are the RGB codes of the colors the customers want.

Print $Q$ lines with one integer each. For each customer request, print the number of the machine's shade that is closest to the requested color. The machine's shades are numbered $0$ to $N-1$ in the order they appear in the input. If two shades are the same distance away, print the one with the smaller number.