커피우유

W유업에서 판매하는 삼각뿔 모양의 커피우유가 있다. 커피우유의 용량은 커피우유가 차지하는 공간의 경계와 내부에 있는 모든 격자점의 개수이다.

W유업 커피우유의 판매 10주년을 맞아 기존 커피우유를 $K$배한 신제품을 출시하려고 한다. 기존 커피우유는 3차원 공간에서 점 $P$, $Q$, $R$, $S$를 꼭짓점으로 하는 삼각뿔 모양이고, 신제품은 네 꼭짓점의 좌표 $(x, y, z)$를 각각 $K$배한 점 $(Kx, Ky, Kz)$을 꼭짓점으로 하는 삼각뿔 모양이다.

$K$의 후보가 $N$개 주어졌을 때, $K$를 각 후보로 선정하여 만든 신제품의 용량을 구해 보자.

답이 매우 클 수 있으므로, $1\,003\,003\,001$로 나눈 나머지를 출력한다.

첫 번째 줄에 $K$의 후보 수 $N$이 주어진다. ($1 \le N \le 200\,000$)

두 번째 줄에 $P$의 $x$축, $y$축, $z$축 좌표를 나타내는 정수 $x_P$, $y_P$, $z_P$가 공백으로 구분되어 주어진다. ($-100 \le x_P, y_P, z_P \le 100$)

세 번째 줄에 $Q$의 $x$축, $y$축, $z$축 좌표를 나타내는 정수 $x_Q$, $y_Q$, $z_Q$가 공백으로 구분되어 주어진다. ($-100 \le x_Q, y_Q, z_Q \le 100$)

네 번째 줄에 $R$의 $x$축, $y$축, $z$축 좌표를 나타내는 정수 $x_R$, $y_R$, $z_R$가 공백으로 구분되어 주어진다. ($-100 \le x_R, y_R, z_R \le 100$)

다섯 번째 줄에 $S$의 $x$축, $y$축, $z$축 좌표를 나타내는 정수 $x_S$, $y_S$, $z_S$가 공백으로 구분되어 주어진다. ($-100 \le x_S, y_S, z_S \le 100$)

여섯 번째 줄에 $K$의 후보를 나타내는 $N$개의 정수 $C_1$, $C_2$, $\cdots$, $C_N$이 공백으로 구분되어 주어진다. ($1 \le C_i \le 10^9$)

삼각뿔 $PQRS$의 부피는 $0$보다 크다.

$K$를 각 후보로 선정하여 만든 신제품의 용량을 $1\,003\,003\,001$로 나눈 나머지를 공백으로 구분하여 출력한다.