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

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

독사의 탈주 timer 2초 memory 64MB

독사의 탈주 2초 64MB