시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB0000.000%

문제

Чтобы стать настоящим джедаем, каждый джедай должен не только искусно владеть мечом, но еще и обладать незаурядными умственными способностями. Безупречно знать физику, математику и информатику, а также уметь решать сложные задачи.

Одна из таких джедайских задач по информатике состоит в следующем.

Вам даны $n$ чисел и $m$ запросов. Запрос представляет из себя следующее: это строка, состоящая из цифр и знаков вопроса.

Ответ на запрос получается следующим образом:

  1. Подставим вместо знаков вопросов всевозможные комбинации цифр, получим числа-подзапросы.
  2. Для каждого числа-подзапроса найдем, сколько чисел из заданных $n$ больше либо равны, чем этот подзапрос.
  3. Просуммируем все ответы на подзапросы.

Данная сумма и будет являться ответом на запрос.

Следует заметить, что если в запросе содержится $k$ знаков вопроса, то получится $10^k$ подзапросов.

Обратите внимание, что подзапросы запросов могут содержать ведущие нули.

А вы сможете решить эту задачу и стать настоящим джедаем?

입력

В первой строке находятся два натуральных числа $n$, $m$ ($1 \le n, m \le 10^5$) --- количество чисел и количество запросов.

В следующей строке заданы $n$ целых чисел $a_i$ ($1 \le a_i < 10^9$). Все числа даны без ведущих нулей.

В каждой из следующих $m$ строк задана непустая строка-запрос, состоящих из цифр и знаков вопроса. Длины строк не превосходят $9$.

출력

В $m$ строках выведите ответы на соответствующие запросы.

예제 입력 1

5 5
10 100 23 1 60
?
0?1
70?
6?
00

예제 출력 1

42
21
0
11
5

예제 입력 2

10 4
1 2 3 66 10 20 34 48 50 103
2?1
0?1
???
??0

예제 출력 2

0
37
347
41