== include(page="template/taskheader" task_id="rk") ==

Se dau $N$ numere naturale. Sa se raspunda la $Q$ intrebari de forma: Cate dintre cele $N$ numere dau restul $R$ la impartirea cu $2^k^$?

Se dau $N$ numere naturale. Sa se raspunda la $Q$ intrebari de forma: Cate dintre cele $N$ numere dau restul $R$ la impartirea cu $2^K^$?

h2. Date de intrare

Fişierul de intrare $rk.in$ va contine pe prima linie numarul $N$. A doua linie va contine $N$ numere naturale. Cea de-a treia linie va contine numarul de intrebari $Q$, iar pe urmatoarele $Q$ linii se vor afla cate doua numere naturale $R$ si $k$ cu semnificatia din enunt.

Fişierul de intrare $rk.in$ va contine pe prima linie numarul $N$. A doua linie va contine $N$ numere naturale. Cea de-a treia linie va contine numarul de intrebari $Q$, iar pe urmatoarele $Q$ linii se vor afla cate doua numere naturale $R$ si $K$ cu semnificatia din enunt.

h2. Date de ieşire

* Toate numerele din fisierul de intrare sunt in intervalul $[0, 2 000 000 000]$
* $1 ≤= N ≤= 200 000$
* $1 ≤= Q ≤= 100 000$

* $0 ≤= k ≤ 32$
* $0 ≤= R ≤ 2^k^$

* $0 ≤= K ≤ 32$
* $0 ≤= R ≤ 2^K^$

* Pentru 20% din teste $N ≤= 1 000$ si $Q ≤= 1 000$

* Pentru 40% din teste $k ≤ 16$

* Pentru 40% din teste $K ≤ 16$

h2. Exemplu