A. The Curse of the Baskervilles
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The foggy moors of Devonshire hold a secret that has haunted the Baskerville bloodline for centuries.

Every generation, a new creature appears, and every generation, the family physician records the creature's genetic makeup as a string of length $$$M$$$. These records are kept in the Great Hall, forming a chronological archive of $$$N$$$ observations: $$$S_1, S_2, \dots, S_N$$$.

Sherlock Holmes has discovered that the creature's genes do not change randomly. They follow an ancient, ritualistic mutation pattern known as the "Descent of the Beast" .

If a creature $$$A$$$ is the direct progenitor of creature $$$B$$$, then for every gene position $$$i$$$, the transition must obey these laws:

The Fallen Gene : A type '1' gene is dominant but unstable; its child can remain a '1' or degrade into a '0'.

The Alpha Spark: A type '0' gene usually remains '0', but once in a millennium, it sparks into an Alpha Gene, denoted as '?'.

The Alpha's Burden: An Alpha Gene '?' is too powerful to sustain itself; its child cannot be another '?'. It must revert to either a '0' or a '1'.

Holmes has $$$Q$$$ new samples from his latest clash on the moors. For each sample string $$$X$$$, he tasks you, his trusted assistant, with two investigations:

Type 1: How many recorded strings $$$S_i$$$ in the archives could have been a direct parent of $$$X$$$?

Type 2: How many recorded strings $$$S_i$$$ in the archives could be a direct child of $$$X$$$?

Input

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \le N \le 2 \cdot 10^5, 1 \le M \le 13$$$) — the number of historical records and the length of the genetic strings.

Each of the next $$$N$$$ lines contains a string $$$S_i$$$ of length $$$M$$$ consisting of characters 0, 1, and ?. These are the recorded observations in the Great Hall.

The next line contains an integer $$$Q$$$ ($$$1 \le Q \le 10^6$$$) — the number of Sherlock's investigations.

Each of the next $$$Q$$$ lines contains an integer $$$T$$$ ($$$T \in \{1, 2\}$$$) and a string $$$X$$$ of length $$$M$$$, representing the query type and the sample string to be analyzed.

Output

For each query, output a single line containing an integer representing the count of recorded strings $$$S_i$$$ that satisfy the condition for Type $$$T$$$.

Example
Input
9 2
11
00
10
01
?0
0?
?1
1?
??
8
1 ?1
2 ?1
1 ?0
2 ?0
1 ??
2 ??
1 11
2 11
Output
2
4
3
4
1
4
4
4