Background

Little $L$ once created the following problem:

• Given an integer sequence $c$ of length $4$, determine if there exists an integer sequence $a$ of length $4$ such that $0 \le a_i \le c_i$ and $(((a_1 \, \text{and} \, a_2) \, \text{xor} \, a_3) \, \text{or} \, a_4 = m$.

After seeing this, Little $C$ felt that this digit DP problem was very standard and uninteresting. Little $L$ then modified the order of bitwise operations in the problem above and created many more problems.

Little $C$ could not take it anymore: "Can you stop creating template digit DP problems?"

Little $L$ had no choice but to hand this pile of problems over to you. However, to increase the challenge, you now need to calculate the answer for all possible $c_i$ and find their sum.

Description

Given a string $s$ of length $n-1$, for a non-negative integer sequence $a$ of length $n$, define its generated sequence $b$ as:

• $b_1 = a_1$;
• For $i > 1$:
  • If $s_{i-1} = A$, then $b_i = b_{i-1} \, \text{and} \, a_i$.
  • If $s_{i-1} = O$, then $b_i = b_{i-1} \, \text{or} \, a_i$.
  • If $s_{i-1} = X$, then $b_i = b_{i-1} \, \text{xor} \, a_i$.

Given a non-negative integer $k$. There are $q$ queries. For each query, given $m$, find how many integer sequences $c$ of length $n$ satisfy:

• For $1 \le i \le n$, $0 \le c_i < 2^k$.
• There exists at least one integer sequence $a$ of length $n$ such that:
  • For $1 \le i \le n$, $0 \le a_i \le c_i$.
  • For the generated sequence $b$ of $a$, $b_n = m$.

Since the answer can be very large, you only need to output the result modulo $2^{32}$.

Input

The first line contains three integers $n, k, q$.

The second line contains a string $s$ of length $n-1$.

The next $q$ lines each contain a query $m$.

Output

Output $q$ lines, each containing a non-negative integer representing the result modulo $2^{32}$.

Examples

Input 1

3 1 2
OA
0
1

Output 1

8
3

Input 2

4 2 2
XOA
1
2

Output 2

189
112

Input 3

4 2 3
XAO
1
2
3

Output 3

237
176
143

Input 4

10 10 3
AOOXOAOXA
749
666
135

Output 4

4239261913
1948492800
2799056799

Constraints

This problem uses bundled testing. You will only receive points for a subtask if you pass all test cases within that subtask.

For $100\%$ of the data, $2 \le n \le 1000$, $1 \le q \le 1000$, $1 \le k \le 30$, $0 \le m < 2^k$.