교묘한 수

교묘한 수(sly number)는 각 원소가 ${0, 1, 2}$ 에 속하는 정수 $N$개로 이루어진 배열 $A$이다. 예를 들어 $A = (1, 1, 0, 2)$는 $A[0] = 1$, $A[1] = 1$, $A[2] = 0$, $A[3] = 2$인 교묘한 수이다.

교묘한 수가 $A[0] = 1$이고 모든 $i = 1, 2, \dots, N-1$에 대해 $A[i] = 0$이면, 이 수를 $ONE$이라고 부른다.

두 교묘한 수 $A$와 $B$에 대해, 별 곱(Star Multiplication) $A \star B$는 길이가 $N$인 배열 $C$를 다음과 같이 만든다.

$$C[k] = \sum_{i=0}^{k} A[i]\cdot B[k-i] ;+; \sum_{i=k+1}^{N-1} A[i]\cdot B[N+k-i]$$

결과 $C$ 역시 길이가 $N$인 배열이지만 교묘한 수가 아닐 수도 있다(원소가 $2$보다 클 수 있다). 결과는 양의 정수 $Q$로 원소별로 나눈 나머지를 취한다.

$$(C \bmod Q)[i] = C[i] \bmod Q$$

교묘한 수 $A$와 나머지 연산의 법 $Q$가 주어졌을 때, 다음을 만족하는 역 교묘한 수 $B$, 즉 원소가 다시 ${0, 1, 2}$ 에 속하는 교묘한 수 $B$를 찾고자 한다.

$$(A \star B) \bmod Q = ONE$$

주어진 각 $A$와 $Q$에 대해, 이러한 역 교묘한 수 $B$가 존재하는지만 판정하면 된다.

첫째 줄에 테스트 케이스의 개수 $K$가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫째 줄에는 공백으로 구분된 두 정수 $Q$ ($2 \le Q \le 100$)와 $N$ ($5 \le N \le 50$)이 주어진다. 둘째 줄에는 교묘한 수 $A$를 이루는 $N$개의 정수가 공백으로 구분되어 주어지며, 각 원소는 ${0, 1, 2}$ 에 속한다.

각 테스트 케이스마다 한 줄씩 출력한다. 역 교묘한 수가 존재하면 A solution can be found을, 그렇지 않으면 No solution을 출력한다.

$Q = 2$, $N = 5$, $A = (1, 0, 1, 0, 1)$인 경우, 가능한 역 교묘한 수 중 하나는 $B = (0, 0, 1, 1, 1)$이다.