D. Wu
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Чилден придумал легендарную историю и пытается продать свою подделку — ожерелье с «Wu» семье Касура. Но мистер Касура пытается разузнать всю правду из истории Чилдена. Поэтому он задаст несколько вопросов Чилдену о его так называемом «личном сокровище».

Это «личное сокровище» представляет собой мультимножество $$$S$$$ из $$$m$$$ «01-строк».

«01-строка» — строка, которая состоит из $$$n$$$ символов «0» и «1». Например, если $$$n=4$$$, то «0110», «0000», и «1110» являются «01-строками», но «00110» (в ней $$$5$$$ символов, а не $$$4$$$) и «zero» (неразрешенные символы) не являются.

Обратите внимание, что мультимножество $$$S$$$ может содержать одинаковые элементы.

Иногда мистер Касура будет давать «01-строку» $$$t$$$ и спрашивать Чилдена количество строк $$$s$$$ в мультимножестве $$$S$$$ таких, что «Wu»-стоимость пары «01-строк» $$$(s, t)$$$ не больше чем $$$k$$$.

Миссис Касура и мистер Касура считают, что, если $$$s_i = t_i$$$ ($$$1\leq i\leq n$$$), то «Wu»-стоимость пары символов равна $$$w_i$$$, иначе — $$$0$$$. «Wu»-стоимость пары «01-строк» равняется сумме всех «Wu»-стоимостей пар их символов. Заметьте, что длина каждой «01-строк» равняется $$$n$$$.

Например, если $$$w=[4, 5, 3, 6]$$$, «Wu» от («1001», «1100») равно $$$7$$$, потому что эти строки имеют одинаковые символы только в первой и третьей позициях, значит $$$w_1+w_3=4+3=7$$$.

Вам нужно помочь Чилдену ответить на запросы мистера Касуры. То есть найти количество строк в мультимножестве $$$S$$$ таких, что «Wu»-стоимость пары не больше $$$k$$$.

Входные данные

Первая строка содержит три целых числа $$$n$$$, $$$m$$$ и $$$q$$$ ($$$1\leq n\leq 12$$$, $$$1\leq q, m\leq 5\cdot 10^5$$$) — длина «01-строк», размер мультимножества $$$S$$$ и количество запросов.

Вторая строка содержит $$$n$$$ целых чисел $$$w_1, w_2, \ldots, w_n$$$ ($$$0 \le w_i \le 100$$$) — стоимость $$$i$$$-го символа.

Каждая из следующих $$$m$$$ строк содержит «01-строку» $$$s$$$ длины $$$n$$$ — строка в мультимножестве $$$S$$$.

Каждая из следующих $$$q$$$ строк содержит «01-строку» $$$t$$$ длины $$$n$$$ и целое число $$$k$$$ ($$$0\leq k\leq 100$$$) — запрос.

Выходные данные

Для каждого запроса выведите ответ на него.

Примеры
Входные данные
2 4 5
40 20
01
01
10
11
00 20
00 40
11 20
11 40
11 60
Выходные данные
2
4
2
3
4
Входные данные
1 2 4
100
0
1
0 0
0 100
1 0
1 100
Выходные данные
1
2
1
2
Примечание

В первом примере мы имеем:

«Wu» от («01», «00») равно $$$40$$$.

«Wu» от («10», «00») равно $$$20$$$.

«Wu» от («11», «00») равно $$$0$$$.

«Wu» от («01», «11») равно $$$20$$$.

«Wu» от («10», «11») равно $$$40$$$.

«Wu» от («11», «11») равно $$$60$$$.

В первом запросе пары («11», «00») и («10», «00») удовлетворяют условие поскольку «Wu» не больше $$$20$$$.

Во втором примере все пары удовлетворяют условие.

В третьем примере пары («01», «11») и («01», «11») удовлетворяют условие. Обратите внимание, что поскольку строка «01» встречается два раза в мультимножестве, то ответ $$$2$$$, а не $$$1$$$.

В четвертом примере, поскольку $$$k$$$ увеличилось, то пара («10», «11») тоже удовлетворяет условие.

В пятом примере, поскольку $$$k$$$ увеличилось, то пара («11», «11») тоже удовлетворяет условие.