주인장과 마법의 수

주인장은 $n$개의 마법의 수를 가지고 있다. $i$번째 수 $a\_i$는 길이가 $i$인 이진 문자열로 나타낼 수 있고, 이 문자열은 앞에 0이 여러 개 붙어도 된다. 이 이진 문자열들을 뒤집어서 이어 붙이면 길이가 $\frac{n (n + 1)}{2}$인 긴 문자열 $s$가 된다. $s\left[\frac{i (i - 1)}{2}\right]$부터 $s\left[\frac{i (i + 1)}{2} - 1\right]$까지의 부분 문자열은 $a\_i$의 이진 표현이며, 가장 낮은 자리부터 가장 높은 자리 순서로 되어 있다. 긴 문자열 $s$의 인덱스는 0부터 시작한다.

어느 날, 린은 주인장의 마법의 수를 프로그램에 입력해서 $n$개의 새로운 마법의 수를 만들려고 한다. $i$번째 새로운 수는 $b\_i$이다. 다음은 C와 비슷한 언어로 작성된 프로그램의 코드이다.

for (int i = 1; i <= n; i++) {
  b[i] = 0,
  flag[i] = 0;
}

for (int i = 1; i <= n; i++) {
  for (int j = 1; j <= n; j++) {
    if (((1 << (j - 1)) & a[i]) > 0) {
      if (!flag[i]) {
        b[i] = b[j],
        flag[i] = 1;
      } else {
        b[i] = b[i] & b[j];
      }
    }
  }
  b[i] = b[i] ^ (1 << (i - 1));
}

위 코드에서 "x << y"는 왼쪽 시프트 연산이며, x에 $2^{\texttt{y}}$를 곱하는 것과 같다. "x & y"는 비트 AND, "x ^ y"는 비트 XOR이다. 수 $a\_i$와 $b\_i$는 임의로 많은 비트를 가질 수 있다고 가정한다.

그 후, 린은 $q$개의 질문을 하려고 한다. $i$번째 질문은 수 $c\_i$이며, 이는 길이가 $\mathit{len}\_i$인 이진 문자열로 나타낼 수 있고 앞에 0이 여러 개 붙어도 된다. 이 이진 문자열들을 뒤집어서 이어 붙이면 길이가 $L\_q$인 긴 문자열 $t$가 되며, 여기서 $L\_k = \sum\limits\_{i = 1}^{k} \mathit{len}\_i$이다. $t\left[L\_{i - 1}\right]$부터 $t\left[L\_i - 1\right]$까지의 부분 문자열은 $c\_i$의 이진 표현이며, 가장 낮은 자리부터 가장 높은 자리 순서로 되어 있다. 긴 문자열 $t$의 인덱스는 0부터 시작한다.

각 질문에 대해 린은 일리아에게 수 $d\_i$를 계산해 달라고 부탁한다.

for (int i = 1; i <= q; i++) {
  d[i] = 0;
  for (int j = 1; j <= min (n, len[i]); j++) {
    if (((1 << (j - 1)) & c[i]) > 0) {
      d[i] = d[i] | b[j];
    }
  }
}

여기서 "x | y"는 비트 OR이다. 수 $c\_i$와 $d\_i$는 임의로 많은 비트를 가질 수 있다고 가정한다.

$i$번째 질문의 답은 $d\_i$의 이진 표현에서 1의 개수이다. 일리아가 모든 질문에 답하도록 도와주자!

입력의 첫째 줄에는 마법의 수의 개수와 긴 문자열 $s$에 있는 1의 개수를 나타내는 두 정수 $n$과 $m$이 주어진다 ($1 \leq n \leq 5000$, $1 \leq m \leq 10^6$).

둘째 줄에는 $m$개의 정수가 주어지며, $i$번째 정수 $p\_i$는 $s[p\_i] = 1$임을 나타낸다. $s$의 나머지 자리는 모두 0이다 ($0 \leq p\_i < \frac{n (n + 1)}{2}$, 모든 $p\_i$는 서로 다르다).

셋째 줄에는 질문의 개수와 긴 문자열 $t$에 있는 1의 개수를 나타내는 두 정수 $q$와 $r$이 주어진다 ($1 \le q \le 5000$, $1 \le r \le 10^6$).

넷째 줄에는 $q$개의 정수가 주어지며, $i$번째 정수 $\mathit{len}\_i$는 $i$번째 질문 $c\_i$의 이진 표현의 길이를 나타낸다 ($1 \leq \mathit{len}\_i \leq 10^9$). $L\_q = \sum\limits\_{i = 1}^{q} \mathit{len}\_i$가 $10^9$ 이하임이 보장된다.

다섯째 줄에는 $r$개의 정수가 주어지며, $i$번째 정수 $z\_i$는 $t[z\_i] = 1$임을 나타낸다. $t$의 나머지 자리는 모두 0이다 ($0 \le z\_i < L\_q$, 모든 $z\_i$는 서로 다르다).

각 질문 $i$에 대해 $d\_i$의 이진 표현에서 1의 개수를 한 줄에 하나씩 출력한다.