독사 탈출

JOI 연구소에는 독사가 $2^L$마리 있다. 독사에는 $0, 1, \ldots, 2^L - 1$의 번호가 붙어 있다. 각 독사는 머리부터 꼬리까지 $L$개의 부분으로 나뉘고, 각 부분의 색은 파란색 아니면 빨간색이다. 독사 $i$의 번호를 이진법으로 $i = \sum_{k=1}^{L} c_k 2^{L-k}$ ($0 \le c_k \le 1$)라고 쓰면,

• $c_k = 0$이면 독사 $i$의 머리에서 $k$번째 부분은 파란색이고,
• $c_k = 1$이면 독사 $i$의 머리에서 $k$번째 부분은 빨간색이다.

각 독사에는 독성이라고 부르는 $0$ 이상 $9$ 이하의 정수가 하나씩 정해져 있다. 숫자 $0$부터 $9$까지로 이루어진 길이 $2^L$의 문자열 $S$가 주어진다. $S$의 $i$번째 문자($1 \le i \le 2^L$)는 독사 $i - 1$의 독성이다.

독사는 재빨라서 JOI 연구소를 자주 탈출한다. 연구소 근처에 사는 사람들은 탈출하는 독사를 목격하면 연구소에 민원을 넣는다.

$Q$일 동안 들어온 민원 목록이 주어진다. $d$번째 날($1 \le d \le Q$)의 민원은 문자 $0$, $1$, $?$로 이루어진 길이 $L$의 문자열 $T_d$다.

• $T_d$의 $j$번째 문자($1 \le j \le L$)가 $0$이면, $d$번째 날에 연구소를 탈출한 모든 독사의 $j$번째 부분이 파란색이라는 뜻이다.
• $T_d$의 $j$번째 문자가 $1$이면, $d$번째 날에 연구소를 탈출한 모든 독사의 $j$번째 부분이 빨간색이라는 뜻이다.
• $T_d$의 $j$번째 문자가 $?$이면, $d$번째 날에 탈출한 독사의 $j$번째 부분에 관한 정보가 없다는 뜻이다.

모든 민원은 정확하다. 탈출한 독사는 모두 같은 날 연구소 직원이 붙잡았다. 같은 독사가 다른 날 다시 탈출할 수도 있다.

JOI 연구소의 소장인 K 교수는 독사 탈출의 위험도를 추정하려고, 날마다 탈출했을 가능성이 있는 독사의 독성 합을 알고 싶어 한다. 즉 $d$번째 날에는 $T_d$의 조건과 모순되지 않는 모든 독사의 독성을 더한 값을 구해야 한다.

독사의 독성을 나타내는 문자열 $S$와 $Q$일 동안의 민원 목록이 주어질 때, 날마다 탈출했을 가능성이 있는 독사의 독성 합을 계산하는 프로그램을 작성하시오.

이 문제는 메모리 제한이 작다는 점에 주의하라.

표준 입력으로 다음 데이터를 읽는다.

• 첫째 줄에 정수 $L$과 $Q$가 공백으로 구분되어 주어진다. 각각 독사 한 마리의 부분 개수와 민원이 들어온 날의 수다.
• 둘째 줄에 길이 $2^L$의 문자열 $S$가 주어진다. 독사의 독성을 나타낸다.
• 이어지는 $Q$개의 줄 중 $d$번째 줄($1 \le d \le Q$)에 길이 $L$의 문자열 $T_d$가 주어진다. $d$번째 날의 민원이다.

표준 출력에 $Q$개의 줄을 출력한다. $d$번째 줄에는 $d$번째 날에 탈출했을 가능성이 있는 독사의 독성 합을 정수로 출력한다.

• $1 \le L \le 20$
• $1 \le Q \le 1\,000\,000$
• $S$는 길이 $2^L$의 문자열이다.
• $S$는 문자 $0, 1, 2, 3, 4, 5, 6, 7, 8, 9$로만 이루어진다.
• $T_d$는 길이 $L$의 문자열이다 ($1 \le d \le Q$).
• $T_d$는 문자 $0, 1, ?$로만 이루어진다 ($1 \le d \le Q$).