34176번 - 이 대회에 원이 등장할 수 없는 이유는? 서브태스크

문제

파이널대회여서

이번에는 하늘이가 무려 MatKor Cup에 참가한다. 또다시 하늘이가 MatKor에 진심인 모습에 감격한 세준이는 하늘이를 위해 새로운 문제를 만들어 이진 원정대를 결성하려 했다. 하지만 원이 등장할 수 없기 때문에 이진 정대 톡방을 만들어 아래 문제를 풀기로 했다.

실제 만들어진 이진 정대 톡방이다.

먼저 임의의 $N$비트 정수 $x$에 대해 적용되는 몇 가지 연산을 아래와 같이 정의하자.

1. 임의의 길이 $N$의 순열^* $\sigma =\left\{ \sigma_i \right\}$에 대해, $N$비트 정수 $\sigma x$는 $i$번째 비트가 $x$의 $\sigma_i$번째 비트와 같도록 정의한다.
2. 임의의 $N$비트 정수 $v$에 대해, $x\oplus v$는 $x$와 $v$ 간의 bitwise XOR 연산이다.

예를 들어 $x=1001_{\left( 2 \right)}$이고 $\sigma =\left( 1,3,4,2 \right)$라면, $\sigma x=0101_{\left( 2 \right)}$이다. 여기서 $\sigma x$의 1ドル$번째 비트가 0ドル$이 아니라 1ドル$임에 유의하라. 정수 $x$의 $i$번째 비트의 값은 $\left\lfloor \frac{x}{2^{i-1}} \right\rfloor \bmod 2$이다.

위의 정의를 따르는 임의의 $\sigma ,v$에 대해, 두 연산을 묶어 아래와 같은 함수 $g_{\sigma ,v}$를 정의하자.

\[g_{\sigma ,v}=\left( \sigma x \right)\oplus v\]

당신은 함수 $f$를 알고 있다. $f$는 $N$비트 정수 하나를 입력받아 0ドル$ 또는 1ドル$을 출력하는 함수이다. 만약 $N$비트 정수를 입력받아 $N$비트 정수를 출력하는 임의의 함수 $h$에 대해, 어떤 $N$비트 정수 $x$에 대해서도 $\left( f\circ h \right)\left( x \right) =f\left( x \right)$라면, 이러한 $h$를 $f$에 의해 무효화된다고 한다.

당신은 다음 조건이 성립하도록 길이가 $M$인 목록 $H=\left[ \left( \sigma^1,v_1 \right) ,\left( \sigma^2,v_2 \right) ,\cdots ,\left( \sigma^M,v_M \right) \right]$를 구성했다.

1. $\sigma^1,\cdots ,\sigma^M$는 모두 길이 $N$의 순열이다.
2. $v_1,\cdots ,v_M$은 모두 $N$비트 정수이다.
3. 모든 $g_{\sigma^1,v_1},\cdots ,g_{\sigma^M,v_M}$는 $f$에 의해 무효화된다.
4. $f$에 의해 무효화되는 임의의 $g_{\sigma ,v}$에 대해, 어떤 1ドル$ 이상 $M$ 이하의 정수로 구성된 유한한 길이 $l$의 수열 $\left\{ a_i \right\}$가 존재하여 $g_{\sigma ,v}\circ g_{\sigma^{a_1},v_{a_1}}\circ g_{\sigma^{a_2},v_{a_2}}\circ\cdots\circ g_{\sigma^{a_l},v_{a_l}}$가 항등함수이다.

그런데 $H$를 적어 둔 종이가 MatKor 출제진에 의해 의도적으로 훼손되었다. 모든 $v_i$ 값들이 교묘하게 지워져 남은 정보는 $\sigma^1,\sigma^2,\cdots ,\sigma^M$ 뿐이었다.

시련이 닥쳤지만 실험은 계속되어야 한다. 논문을 쓰지 못하면 졸업할 수 없기 때문이다. $f$와 $\sigma^1,\sigma^2,\cdots ,\sigma^M$이 주어질 때, 아래 쿼리에 답해 보자.

• $k\ \pi_1\ \pi_2\ \cdots\ \pi_N$: 음이 아닌 정수 $k$와 길이 $N$의 순열 $\left\{ \pi_i \right\}$에 대해, $g_{\pi ,v}^{k}$가 $f$에 의해 무효화되도록 하는 $N$비트 정수 $v$의 개수를 998ドル,円 244,円 353$으로 나눈 나머지를 출력하라. 여기서 $g_{\pi ,v}^{0}\left( x \right) =x,g_{\pi ,v}^{n+1}=g_{\pi ,v}^{n}\circ g_{\pi ,v}$이다.

^*길이 $N$의 순열이란 1ドル$ 이상 $N$ 이하의 정수가 한 개씩 포함된 길이 $N$의 수열을 의미한다.

입력

첫 번째 줄에 $N,M(1\leq N,M\leq 20)$이 공백으로 구분되어 주어진다.

두 번째 줄에 길이 2ドル^N$의 이진 문자열이 주어진다. 문자열의 왼쪽에서부터 $i$번째 원소는 $f\left( i-1 \right)$의 값을 나타내고, 양의 정수 $i$의 $j$번째 비트의 값은 $\left\lfloor \frac{i}{2^{j-1}} \right\rfloor\bmod 2$이다.

세 번째 줄부터 $M$ 줄에 걸쳐 각 줄에 길이 $N$의 순열 $\sigma^i$의 원소 $\sigma^i_1,\cdots ,\sigma^i_N$이 순서대로 공백으로 구분되어 주어진다.

$M+3$번째 줄에는 쿼리의 개수 $Q(1\leq Q\leq 1,円 000)$가 주어진다.

$M+4$번째 줄부터 $Q$개의 줄에는 쿼리 $k(0\leq k\leq 10^{18})$과 길이 $N$의 순열 $\pi$의 원소 $\pi_1,\cdots ,\pi_N$이 공백으로 구분되어 주어진다.

출력

첫 번째 줄부터 $Q$ 줄에 걸쳐 각 쿼리마다 정답을 한 줄에 한 개씩 출력한다.

제한

서브태스크

힌트