서로 겹치지 않는 부분집합의 합성

길이가 각각 $N$, $M$인 정수 배열 $A$, $B$와 양의 정수 $P$가 주어진다. 배열의 인덱스는 $0$부터 시작한다.

두 배열 중 하나라도 비어 있으면 결과는 빈 배열이다. 그렇지 않으면 두 배열의 길이를 $\max(N,M)$ 이상인 가장 작은 $2$의 거듭제곱 $L$로 맞추고, 부족한 원소를 $0$으로 채운다.

배열의 각 인덱스를 이진수에서 비트가 $1$인 위치들의 집합 $S$로 나타내자. 길이가 $L$인 배열 $C$를 다음과 같이 정의할 때, 각 $C[S]$를 $P$로 나눈 나머지를 구해 보자.

\[ C[S]=\sum_{\substack{X\cap Y=\varnothing\\X\cup Y=S}}A[X]B[Y]. \]

첫 번째 줄에 테스트 케이스의 수를 의미하는 정수 $T$가 주어진다. $(1 \le T \le 1\,000)$ 각 테스트 케이스는 다음과 같이 주어진다.

첫 번째 줄에 세 정수 $N$, $M$, $P$가 공백으로 구분되어 주어진다. $(0 \le N, M \le 262\,144; 1 \le P \le 2^{31}-1)$ $P$는 소수일 필요가 없다.

두 번째 줄에 배열의 원소 $A_0, A_1, \cdots, A_{N-1}$이 공백으로 구분되어 주어진다. $(-2^{63} \le A_i \le 2^{63}-1)$

세 번째 줄에 배열의 원소 $B_0, B_1, \cdots, B_{M-1}$이 공백으로 구분되어 주어진다. $(-2^{63} \le B_i \le 2^{63}-1)$

모든 테스트 케이스에 대한 $N+M$의 합은 $524\,288$ 이하이다. 빈 배열도 빈 줄을 차지한다. 입력 마지막에 연속한 빈 줄은 생략해도 된다.

각 테스트 케이스마다 첫 번째 줄에 결과 배열 $C$의 길이를 출력한다. 두 번째 줄에 $C$의 각 원소를 $P$로 나눈 나머지를 인덱스 순서대로 공백으로 구분하여 출력한다. 나머지는 $[0,P)$의 값으로 출력한다.

결과가 빈 배열이면 첫 번째 줄에 $0$을 출력하고 두 번째 줄은 빈 줄로 출력한다.