독사의 탈주 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일 동안 주어지는 독사의 정보에 대해, 각 날마다 그 날 탈출한 가능성이 있는 독사들의 위험도 총합을 계산하는 것이다.

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