Let \(M\) be the set of all integers representable in base \(2\) with at most \(B\) digits and \(f : M \to M, f(x) = x \oplus r(x, k_1) \oplus r(x, k_2) \oplus \ldots \oplus r(x, k_N)\), for \(k_1, k_2, \ldots, k_N\) given constants and \(r : (M \times \mathbb{N}) \to M, r(x, k)\) perform a cyclic rotation by \(k\) positions to the left of \(x\)'s digits in base \(2\). The bitwise xor was denoted with \(\oplus\).

Also denote \(f^1(x)=f(x)\) and \(f^m(x) = f^{m-1}(f(x))\) for \(m > 0\).

For \(Q\) queries you will be given a number \(y\) in base \(2\), with \(B\) digits, but possibly with leading zeros, and an integer \(m\) and you must print \(f^m(y)\) with \(B\) digits in base \(2\).

Input:

The first line contains three integers \(B, N, Q\) .

The second line contains \(N\) integers \(k_1, k_2, \ldots k_N\).

The next \(Q\) lines contain \(y\) and \(m\).

Output:

Print \(Q\) lines, each containing the answer for a query. Note that it must be prefixed with \(0\)s if it has less than \(B\) digits.

Notes and contraints:

\(1 \leq B, N, Q \leq 500\)

\(1 \leq M \leq 10^{18}\)

\(0 \leq k_i \leq B - 1 \ \forall\ 1 \leq i \leq N\)

For \(10\) points, \(M \leq 10\)

For another \(10\) points, \(B, N, Q \leq 40\)

For another \(20\) points, \(B, N, Q \leq 100\)

For another \(35\) points, \(B, N, Q \leq 200\)