독사의 탈주 timer 2초 memory 64MB

조이연구소에서는 ​$2^L$마리의 독사를 기르고 있으며, 각각 $0, 1, \cdots, 2^L-1$의 번호가 매겨져있다. 

모든 독사는 머리부터 발끝까지 $L$개의 부분으로 나누어져 있으며, 각 부분은 파랑 또는 빨간색이 칠해져 있다. 

특별히 $i$번째 독사의 생김새는 $i$를 $2$진수로 표기했을 때, $k$번째 자릿수가 $0$이라면 $k$번째 부분은 파란색, $1$이라면 빨간색이다. 

예를 들어, $L=3$인 경우 $0$번째 뱀은 모든 부분이 파란색이고, $6$번째 뱀은 빨강, 빨강, 파랑 순서대로 칠해져 있다.

각 독사는 위험도가 $0$ 이상 $9$ 이하의 정수 값으로 정해져 있다. 

$0,1,2,3,4,5,6,7,8,9$로 이루어진 길이 $2^L$의 문자열 $S$가 주어지며, $i$번째 글자$(1 \le i \le 2^L)$는 $i-1$번째 독사의 위험도를 나타낸다.

조이연구소에서는 독사들이 매우 잘 탈출한다. 

때문에 조이연구소는 하루에 한 번씩 탈출한 독사의 정보를 수집한 뒤, 그 정보를 바탕으로 위험도를 계산하여 독사 회수에 필요한 장비를 준비하고 있다.

당신은 Q일 동안 탈출한 독사들에 대한 정보가 주어진다. 

$d$일째 ($1 ≦ d ≦ Q$)에 접수 된 정보는 $0, 1, ?$로 이루어진 길이 $L$인 문자열 $T_d$​로 표현되고, 각 글자는 다음과 같은 의미를 가진다.

• $T_d$​의 $j$번째 문자가 $0$인 경우는 $d$일째에 탈출한 모든 독사의 $j$번째 부분이 파란색이다.

• $T_d$​의 $j$번째 문자가 $1$인 경우는 $d$일째에 탈출한 모든 독사의 $j$번째 부분이 빨간색이다.

• $T_d$​의 $j$번째 문자가 $?$인 경우는 $d$일째에 탈출한 모든 독사의 $j$번째 부분에 대한 정보가 없다. (빨간색일수도, 파란색일수도 있다)

탈출한 독사는 조이연구소의 직원이 모두 당일에 회수하며, 탈출했다가 돌아온 독사가 다음날 이후에 다시 탈출할 수 있다.

당신의 임무는 $Q$일 동안 주어지는 독사의 정보에 대해, 각 날마다 그 날 탈출한 가능성이 있는 독사들의 위험도 총합을 계산하는 것이다.

메모리 제한이 작은 것에 유의하자.