30922번 - 커피우유

문제

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円$로 나눈 나머지를 공백으로 구분하여 출력한다.

제한

힌트