Let M be the set of all integers representable in base 2 with at most B digits and f:M→M,f(x)=x⊕r(x,k1)⊕r(x,k2)⊕…⊕r(x,kN), for k1,k2,…,kN given constants and r:(M×N)→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 ⊕.
Also denote f1(x)=f(x) and fm(x)=fm−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 fm(y) with B digits in base 2.
Input:
The first line contains three integers B,N,Q .
The second line contains N integers k1,k2,…kN.
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 0s if it has less than B digits.
Notes and contraints:
1≤B,N,Q≤500
1≤M≤1018
0≤ki≤B−1 ∀ 1≤i≤N
For 10 points, M≤10
For another 10 points, B,N,Q≤40
For another 20 points, B,N,Q≤100
For another 35 points, B,N,Q≤200
For the first query, 100⊕001=101.
For the second query we continue with the result and obtain 101⊕011=110.