Coffee Milk

W Dairy sells a coffee milk in the shape of a triangular pyramid. The capacity of the coffee milk is the number of lattice points on the boundary of the space it occupies and inside that space.

To mark the 10th anniversary of the coffee milk, W Dairy plans to release a new product that is the original scaled by $K$. The original is a triangular pyramid with vertices $P$, $Q$, $R$, and $S$ in three-dimensional space. The new product is a triangular pyramid whose vertices are $(Kx, Ky, Kz)$, where $(x, y, z)$ is each vertex of the original multiplied by $K$.

Given $N$ candidate values of $K$, find the capacity of the new product for each candidate.

The answer can be very large, so print the capacity modulo $1\,003\,003\,001$.

The first line contains the number of candidates $N$ for $K$ ($1 \le N \le 200\,000$).

The second line contains the integers $x_P$, $y_P$, and $z_P$, the x, y, and z coordinates of $P$, separated by spaces ($-100 \le x_P, y_P, z_P \le 100$).

The third line contains the integers $x_Q$, $y_Q$, and $z_Q$, the coordinates of $Q$, separated by spaces ($-100 \le x_Q, y_Q, z_Q \le 100$).

The fourth line contains the integers $x_R$, $y_R$, and $z_R$, the coordinates of $R$, separated by spaces ($-100 \le x_R, y_R, z_R \le 100$).

The fifth line contains the integers $x_S$, $y_S$, and $z_S$, the coordinates of $S$, separated by spaces ($-100 \le x_S, y_S, z_S \le 100$).

The sixth line contains the $N$ candidate values $C_1$, $C_2$, $\cdots$, $C_N$ for $K$, separated by spaces ($1 \le C_i \le 10^9$).

The volume of the triangular pyramid $PQRS$ is greater than $0$.

For each candidate $K$, print the capacity of the new product modulo $1\,003\,003\,001$. Separate the answers with spaces.