Sirmod

Enunţ

Alex a învățat la școală despre mai multe șiruri cum ar fi șirul lui Fibonacci. Mai mult, a învățat că poate să își creeze propriul său șir. După ce a făcut asta, fiind mai curios din fire, Alex a studiat mai multe proprietăți ale acestuia, precum și restul numerelor din el la împărțirea cu alte numere, dar nu își poate răspunde la toate întrebările așa că vă roagă pe voi să-l ajutați.

Cerinţe

Se dă un șir format prin relația de recurență $a_i=a_{i-1} \cdot x + y$. Dându-se $Q$ întrebări de forma $l, r, k, m$ de forma câte numere din șirul $a_l \dots a_r$ dau restul $k$ la împărțirea cu $m$, răspundeți eficient la fiecare întrebare, pentru a-l ajuta pe Alex.

Date de intrare

Fișierul de intrare sirmod.in conține pe prima linie trei numere întregi: $a1, x, y$. Pe a doua linie se va afla numărul natural $q$, cu semnificația din enunț. Pe următoarele $q$ linii se vor afla $4$ numere naturale, $l, r, k, m$.

Date de ieşire

În fișierul de ieșire sirmod.out se vor afla $q$ linii, pe linia $i$ aflându-se un singur număr natural, reprezentândrăspunsul la întrebarea $i$.

Restricţii și precizări

• $1 \leq a_1,x,y \leq 10^9$
• $1 \leq q \leq 2 \cdot 10^5$
• $1 \leq m_i \leq 5000$
• $0 \leq k_i < m_i$
• $1 \leq l_i \leq r_i \leq 10^{18}$
  Pentru teste în valoare de $30$ de puncte: $1 \leq q \leq 100, 1 \leq l_i \leq r_i \leq 10^6$
  Pentru teste în valoare de $60$ de puncte: $1 \leq q \leq 5000$

Exemple

sirmod.in

1 2 1
2
1 5 0 31
2 7 3 31

sirmod.out

1
2

Explicații

Primele $7$ numere din șir sunt $1,3,7,15,31,63,127$