Házi feladat

Péter informatika házi feladata a következő függvény megvalósítása:

input: A,B,C,x positive integers
output: y
1.  y=1
2.  while x ≥ C
3.    y=y+1
4.    if x is odd
5.      x=Ax+B
6.    else
7.      x=floor(x/C)
8.    end
9.  end

Néhány egyszerű példát is kapott az (előzetes) teszteléshez:

A=3, B=1, C=2
x=21 ⟶ 64 ⟶ 32 ⟶ 16 ⟶ 8 ⟶ 4 ⟶ 2 ⟶ 1, y=8
x=211 ⟶ 634 ⟶ 317 ⟶ 952 ⟶ 476 ⟶ ... ⟶ 16 ⟶ 8 ⟶ 4 ⟶ 2 ⟶ 1, y=40
x=123321 ⟶ 369964 ⟶ 184982 ⟶ 92491 ⟶ 277474 ⟶ ... ⟶ 16 ⟶ 8 ⟶ 4 ⟶ 2 ⟶ 1, y=75

A=15, B=5, C=10
x=21 ⟶ 320 ⟶ 32 ⟶ 3, y=4
x=211 ⟶ 3170 ⟶ 317 ⟶ 4760 ⟶ 476 ⟶ ... ⟶ 161 ⟶ 2420 ⟶ 242 ⟶ 24 ⟶ 2, y=16
x=123321 ⟶ 1849820 ⟶ 184982 ⟶ 18498 ⟶ 1849 ⟶ ... ⟶ 416 ⟶ 41 ⟶ 620 ⟶ 62 ⟶ 6, y=14

A=7, B=3, C=5
x=21 ⟶ 150 ⟶ 30 ⟶ 6 ⟶ 1, y=5
x=211 ⟶ 1480 ⟶ 296 ⟶ 59 ⟶ 416 ⟶ ... ⟶ 23 ⟶ 164 ⟶ 32 ⟶ 6 ⟶ 1, y=13
x=123321 ⟶ 863250 ⟶ 172650 ⟶ 34530 ⟶ 6906 ⟶ ... ⟶ 21 ⟶ 150 ⟶ 30 ⟶ 6 ⟶ 1, y=17

A függvény valódi felhasználása a következő lesz: adott $A,B,C$ számok esetén $Q$ különböző $[lo,up]$ (zárt) intervallumra kell megadni azt hogy az intervallum összes elemét figyelembe véve mennyi a számolt $y$ -ok minimuma és maximuma. Például:

A=3, B=1, C=2
lo=10, up=100 ⟶ min_y=5, max_y=119
lo=100,up=1000 ⟶ min_y=8, max_y=179
lo=1000,up=10000 ⟶ min_y=11, max_y=262

A=15, B=5, C=10
lo=10,up=100 ⟶ min_y=2, max_y=15
lo=100,up=1000 ⟶ min_y=3, max_y=30
lo=1000,up=10000 ⟶ min_y=4, max_y=52

A=7, B=3, C=5
lo=10,up=100 ⟶ min_y=2, max_y=23
lo=100,up=1000 ⟶ min_y=3, max_y=40
lo=1000,up=10000 ⟶ min_y=5, max_y=48

Segítsünk Péternek!

Bemenet specifikáció

Az első sorban az $A,B,C$ számok vannak. A másodikban $Q$ . Ezután $Q$ sor következik, mindegyikben a megfelelő $lo_{i}$ és $up_{i}$ számokkal ( $i=1,\ldots,Q$ ). A sorokon belül a számok üreshellyel vannak elválasztva.

Kimenet specifikáció

$Q$ sor kiszámolandó mennyiségekkel. Az egy sorban levő számokat üreshellyel válasszuk el egymástól.

Korlátok

$1\le Q \le 100$
$1\le lo,up \le 1\_000\_000$
$1\le up-lo+1 \le 10\_000$
$1\le A,B,C \le 31$
Biztosak lehetünk abban hogy a kapott parameterekkel a számolt hosszak maximuma legfeljebb $1\_000$ és a függvény által meglátogatott számok beleférnek egy 64 bites előjeles egészbe.