Giá trị Wu

Cho một bội tập (multiset) $S$ gồm $m$ xâu nhị phân, mỗi xâu có đúng $n$ ký tự, mỗi ký tự là 0 hoặc 1. Bội tập có thể chứa nhiều phần tử giống hệt nhau.

Cho thêm $n$ số nguyên $w_1,w_2,\dots ,w_n$. Với hai xâu nhị phân $s$ và $t$ cùng độ dài $n$, giá trị Wu của cặp $(s,t)$ là tổng các $w_i$ trên những vị trí mà hai xâu trùng ký tự:

$$\mathrm{W}\mathrm{u}(s,t)=\sum _{i=1}^n{w}_i·[s_i=t_i]$$

Chẳng hạn với $w=[4,5,3,6]$ thì $\mathrm{W}\mathrm{u}(\text{1001},\text{1100})=w_1+w_3=4+3=7$, vì hai xâu chỉ trùng nhau ở vị trí thứ nhất và thứ ba.

Bạn phải trả lời $q$ truy vấn. Mỗi truy vấn cho một xâu nhị phân $t$ độ dài $n$ và một số nguyên $k$: hãy đếm xem có bao nhiêu xâu $s$ trong $S$ thoả mãn $\mathrm{W}\mathrm{u}(s,t)\le k$. Các phần tử giống nhau của $S$ được đếm riêng biệt.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $q$.
• Dòng thứ hai chứa $n$ số nguyên $w_1,w_2,\dots ,w_n$.
• $m$ dòng tiếp theo, mỗi dòng một xâu nhị phân độ dài $n$, là một phần tử của $S$.
• $q$ dòng tiếp theo, mỗi dòng một xâu nhị phân $t$ độ dài $n$ và một số nguyên $k$, mô tả một truy vấn.

Dữ liệu ra

In ra $q$ dòng, dòng thứ $j$ là đáp án cho truy vấn thứ $j$.

Ràng buộc

• $1\le n\le 12$
• $1\le m,q\le 5·{10}^5$
• $0\le w_i\le 100$
• $0\le k\le 100$

Ví dụ