Rotate and Xor

2.3

3 votes
Mathematics, Matrix Transformation, Medium, Linear Algebra
Problem

Let M be the set of all integers representable in base 2 with at most B digits and f:MM,f(x)=xr(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)=fm1(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:

1B,N,Q500

1M1018

0kiB1  1iN

For 10 points, M10

For another 10 points, B,N,Q40

For another 20 points, B,N,Q100

For another 35 points, B,N,Q200

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

For the first query, 100001=101.

For the second query we continue with the result and obtain 101011=110.

Editor Image

?