시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 64 MB 13 6 5 62.500%

문제

JOI Laboratory has 2L poisonous snakes. The snakes are numbered 0, 1, . . . , 2L − 1. Each snake is divided into L parts from the head to the tail. The color of each part is either blue or red. For the poisonous snake i, let i = \(\sum_{k=1}^{L}\)ck2L−k (0 ≤ ck ≤ 1) be the binary expression of i. Then,

  • if ck = 0, the color of the k-th part of the poisonous snake i from the head is blue, and
  • if ck = 1, the color of the k-th part of the poisonous snake i from the head is red.

Each poisonous snake has an integer between 0 and 9, inclusive, called the toxicity. A string S of length 2L consisting of 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 is given. The i-th character (1 ≤ i ≤ 2L) is the toxicity of the poisonous snake i − 1.

Since poisonous snakes are quick, they often escape from JOI Laboratory. Complaints are given to JOI Laboratory by people living near the laboratory who saw poisonous snakes escaping from the laboratory.

You are given a list of complaints for Q days. The complaints for the d-th day (1 ≤ d ≤ Q) is a string Td of length L consisting of 0, 1, ?.

  • If the j-th character (1 ≤ j ≤ L) of Td is 0, this means the j-th part of every poisonous snake escaping from the laboratory on the d-th day is blue,
  • If the j-th character (1 ≤ j ≤ L) of Td is 1, this means the j-th part of every poisonous snake escaping from the laboratory on the d-th day is red, and
  • If the j-th character (1 ≤ j ≤ L) of Td is ?, this means no information was given by people concerning the j-th part of poisonous snakes escaping from the laboratory on the d-th day.

All the complaints are precise information. All the poisonous snakes escaping from the laboratory were kept by the staffs of JOI Laboratory on the same day. It may happen that the same snake escapes on a different day.

In order to estimate the risk of escaping poisonous snakes, Professor K, the executive director of JOI Laboratory, wants to know the sum of toxicities of the snakes which might escape from the laboratory. Your task is to write a program which calculates, given the list of complaints for Q days, the sum of toxicities of the snakes which might escape from the laboratory for each day.

Given the string S describing the toxicities of the poisonous snakes and the list of complaints for Q days, write a program which calculates the sum of toxicities of the snakes which might escape from the laboratory for each day.

Note that the memory limit is small for this task.

입력

Read the following data from the standard input.

  • The first line contains two space separated integers L, Q. They are the number of parts of each poisonous snake and the number of days for the complaints, respectively.
  • The second line contains a string S of length 2L. It describes the toxicities of the poisonous snakes.
  • The d-th line (1 ≤ d ≤ Q) of the following Q lines contains a string Td of length L. It is the complaints of the d-th day.

All input data satisfy the following conditions.

  • 1 ≤ L ≤ 20.
  • 1 ≤ Q ≤ 1 000 000.
  • S is a string of length 2L,
  • The string S consists of 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
  • Td is a string of length L (1 ≤ d ≤ Q).
  • The string Td consists of 0, 1, ? (1 ≤ d ≤ Q).

출력

Write Q lines to the standard output. The d-th line should contain an integer, the sum of toxicities of the snakes which might escape from the laboratory on d-th day.

예제 입력 1

3 5
12345678
000
0??
1?0
?11
???

예제 출력 1

1
10
12
12
36

예제 입력 2

4 8
3141592653589793
0101
?01?
??1?
?0??
1?00
01?1
??10
????

예제 출력 2

9
18
38
30
14
15
20
80

힌트

In this sample input 1, L = 3. There are 23 = 8 poisonous snakes. Each of them is divided into 3 parts. The complaints are given for 5 days.

  • On the first day, the poisonous snakes which might escape from the laboratory is the poisonous snake 0 only. The sum of toxicities is 1.
  • On the second day, the poisonous snakes which might escape from the laboratory are the poisonous snakes 0, 1, 2, 3. The sum of toxicities is 10.
  • On the third day, the poisonous snakes which might escape from the laboratory are the poisonous snakes 4, 6. The sum of toxicities is 12.
  • On the fourth day, the poisonous snakes which might escape from the laboratory are the poisonous snakes 3, 7. The sum of toxicities is 12.
  • On the fifth day, the poisonous snakes which might escape from the laboratory are the poisonous snakes 0, 1, 2, 3, 4, 5, 6, 7. The sum of toxicities is 36.