Diferențe pentru problema/reginald între reviziile #2 si #7

Lui Reginald Barclay îi este frică de transportorul cuantic. Atît de frică încît de fiecare dată cînd poate preferă să ia naveta spațială spre planetă și înapoi spre Enterprise. Într-o zi, în drum spre Bajor, naveta s-a defectat, prăbușindu-se undeva în Kendra. Reginald este acum nevoit să ia antigravul pînă în Rakantha, destinația sa. Este o călătorie lungă, iar șoselele pe Bajor sînt în stare jalnică după lunga ocupație Cardassiană. Reginald își umple timpul în vreme ce pilotul automat îl anunță monoton cîte ore mai sînt pînă la destinație.

El atribuie numerelor de pe bornele kilometrice o putere, astfel: mai întîi găsește cel mai mic divizor diferit de [$1$]. Apoi împarte numărul la acest divizor de cîte ori poate. Apoi caută următorul divizor și împarte numărul rămas de cîte ori poate. El continuă această procedură pînă ce numărul nu mai are divizori mai mari ca [$1$]. Pentru fiecare divizor găsit puterea numărului crește cu [$1$]. De exemplu, pentru numărul [$12$]$ Reginald găsește ca cel mai mic divizor pe [$2$]$. Puterea numărului crește cu [$1$]. Împarțind la doi de cîte ori putem obținem noul număr [$3$]. Următorul divizor este chiar $3$ și puterea crește cu [$1$]. Împărțim numărul la $3$ și procedeul se termină. Astfel, puterea lui $12$ este [$2$].

El atribuie numerelor de pe bornele kilometrice o putere, astfel: mai întîi găsește cel mai mic divizor diferit de [$1$]. Apoi împarte numărul la acest divizor de cîte ori poate. Apoi caută următorul divizor și împarte numărul rămas de cîte ori poate. El continuă această procedură pînă ce numărul nu mai are divizori mai mari ca [$1$]. Pentru fiecare divizor găsit puterea numărului crește cu [$1$]. De exemplu, pentru numărul $12$ Reginald găsește ca cel mai mic divizor pe [$2$]. Puterea numărului crește cu [$1$]. Împarțind la doi de cîte ori putem obținem noul număr [$3$]. Următorul divizor este chiar $3$ și puterea crește cu [$1$]. Împărțim numărul la $3$ și procedeul se termină. Astfel, puterea lui $12$ este [$2$].

Cînd intră pe o nouă autostradă [$i$], Reginald își alege o putere $p[~i~]$. El notează kilometrul de intrare $x[~i~]$, și  apoi calculează pentru fiecare kilometru, începînd cu $x[~i~]$, puterea sa. La ieșire își notează kilometrul de ieșire $y[~i~]$ și puterea $p[~i~]$. Astfel, cînd ajunge in Rakantha, el se trezește cu o listă de $n$ tripleți de forma $(x[~i~], y[~i~], p[~i~])$. Din nefericire el a uitat să își noteze numărul de kilometri calculați cu puterea $p[~i~]$. Puteți să îl ajutați să-l recalculeze?

h2. Date de intrare

Fișierul de intrare $reginald.in$ ...

Pe prima linie a fișierului de intrare $reginald.in$ se găsește [$n$], numărul de segmente de autostradă prin care a trecut Reginald. Pe următoarele $n$ linii vom avea cîte trei numere, reprezentînd x[~i~], kilometrul de intrare pe acel segment, y[~i~], kilometrul de ieșire de pe autostradă, precum și puterea p[~i~] a kilometrilor urmăriți.

h2. Date de ieșire

În fișierul de ieșire $reginald.out$ ...

În fișierul de ieșire $reginald.out$ pentru fiecare segment de autostrada $i$ se cere să se  afișeze numărul de kilometri calculați de Reginald ca avînd puterea p[~i~].

h2. Restricții

* $... ≤ ... ≤ ...$

* $1 ≤ n ≤ 1000000$
* $0 ≤ p[~i~] ≤ 2500$
* $1 ≤ x[~i~] ≤ y[~i~] ≤ 4000000$
* pentru $30%$ din teste $1 ≤ x[~i~] ≤ y[~i~] ≤ 100000$
* pentru $50%$ din teste $1 ≤ x[~i~] ≤ y[~i~] ≤ 1000000$

h2. Exemplu

h2. Exemple

table(example).

|_. reginald.in |_. reginald.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
 
h3. Explicație
 
...

|_. reginald.in |_. reginald.out |_. Explicație |
| 3
1 6 2
5 10 3
3 8 1
| 1
0
5
| Există doar un număr cu putere 2 între 1 și 6 și anume 6.
Nu există nici un număr cu putere 3 între 5 și 10.
Există 5 numere cu putere 1 între 3 și 8 și anume 3, 4, 5, 7, 8.
|
| 5
9 15 2
1 10 0
23 32 3
1 30 4
3 31 1
| 4
1
1
0
16
| Există 4 numere cu putere 2 între 9 și 15 și anume 10, 12, 14, 15.
Există doar un număr cu putere 0 între 1 și 10 și anume 1.
Există doar un număr cu putere 3 între 23 și 32 și anume 30.
Nu există nici un număr cu putere 4 între 1 și 30.
Există 16 numere între 3 și 31 cu putere 1 și anume 2, 3, 4, 5, 7, 8,
9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31
|

== include(page="template/taskfooter" task_id="reginald") ==