multisum

Orice număr natural mai mare decât $2$ poate fi scris ca sumă de numere naturale nenule aflate în ordine strict crescătoare, astfel încât orice termen al sumei, cu excepția primului termen, este un multiplu a termenului precedent din sumă. De exemplu, $27=3+6+18$, unde $6$ este multiplul lui $3$, iar $18$ este multiplul lui $6$. Cum se dorește o descompunere formată dintr-un număr cât mai mare de termeni, vom obține și descompuneri cu $4$ termeni: $27=1+2+8+16$ sau $27=1+2+4+20$ sau $27=1+2+6+18$. Dintre cele trei descompuneri cu $4$ termeni, descompunerea $27=1+2+4+20$ este minimă din punct de vedere lexicografic ($1$ și $2$ sunt la fel în cele $3$ descompuneri, dar $4<6$ și $4<8$). Numărul $30$ poate fi descompus $30=2+4+8+16$. El are o descompunere tot de lungime $4$, dar este mai mare din punct de vedere lexicografic decât oricare dintre descompunerile cu $4$ termeni ale lui $27$ ($2 > 1$).

Cerință

Pentru mai multe seturi de date formate din câte două numere naturale $A$ și $B$, $A \leq B$, se cere să se determine, pentru fiecare set, una dintre următoarele cerințe:
$1)$ numărul maxim de termeni în care pot fi descompuse numerele din intervalul $[A,B]$ după regula descrisă în enunț;
$2)$ numărul de numere din intervalul $[A,B]$ care pot fi descompuse cu un număr maxim de termeni;
$3)$ numărul din intervalul $[A,B]$ care admite o descompunere cu un număr maxim de termeni, minimă din punct de vedere lexicografic.

Date de intrare

Din fișierul multisum.in se citesc, de pe prima linie, două numere $N$ și $C$, despărțite printr-un spațiu, reprezentând numărul de seturi de date și tipul cerinței: $C=1$ pentru cerința $1$, $C=2$ pentru cerința $2$ și $C=3$ pentru cerința $3$. De pe următoarele $N$ linii ale fișierului se citește câte o pereche de numere $A$ și $B$, separate printr-un spațiu.

Date de ieșire

În fișierul multisum.out se va scrie câte o linie pentru fiecare pereche $A,B$ din fișierul de intrare, linie care va conține numărul cerut, conform cerinței: dacă $C=1$, numărul va reprezenta numărul maxim de termeni dintr-o descompunere, dacă $C=2$, numărul va reprezenta numărul de valori din intervalul respectiv care pot fi descompuse cu un număr maxim de termeni, iar dacă $C=3$, numărul va reprezenta acea valoare din intervalul respectiv care admite o descompunere cu un număr maxim de termeni, minimă din punct de vedere lexicografic.

Restricții și precizări

• $0 < N \leq 1 \ 000$;
• $2 < A \leq B \leq 100 \ 000$;
• Suma lungimilor intervalelor din toate seturile unui test nu va depăși $100 \ 000$;
• Pentru rezolvarea corectă a cerinței $1$, se acordă $20\%$ din punctaj, pentru cerința $2$ se acordă $40\%$ din punctaj, iar pentru cerința $3$ se acordă $40\%$ din punctaj;
• Pentru teste în valoare de $30$ de puncte, $N \leq 50, B \leq 1 \ 000$ și suma lungimilor intervalelor din teste nu va depăși $10 \ 000$.

Exemplul 1

multisum.in

1 1
50 60

multisum.out

5

Explicație

Există un singur set de date. Se rezolvă cerința $1$.

Descompunerile maximale ale numerelor din interval au unele $4$ termeni, altele $5$ termeni. Deci cel mai mare număr de termeni este $5$ (și acesta se obține pentru numerele $55$, $57$, $58$ și $59$).

Exemplul 2

multisum.in

1 2
50 60

multisum.out

4

Explicație

Există un singur set de date. Se rezolvă cerința $2$.

Numerele care se pot descompune într-un număr maxim de termeni sunt $55$, $57$, $58$ și $59$. Deci sunt $4$ numere care admit o descompunere maximală.

Exemplul 3

multisum.in

1 3
50 60

multisum.out

55

Explicație

Există un singur set de date. Se rezolvă cerința $3$.

Cele $4$ numere care admit descompuneri maximale sunt:

• $55=1+2+4+16+32$;
• $55=1+2+4+12+36$;
• $55=1+2+4+8+40$;
• $57=1+2+6+12+36$;
• $58=1+3+6+12+36$;
• $59=1+2+8+16+32$.

Cea mai mică sumă din punct de vedere lexicografic este $1+2+4+8+40$ și ea corespunde numărului $55$.

Exemplul 4

multisum.in

3 3
50 50
10 13
16 17

multisum.out

50
11
17

Explicație

Sunt $3$ seturi de date. Se rezolvă cerința $3$.

• Intervalul $[50, 50]$ conține doar numărul $50$ care admite o singură descompunere maximală (cu $4$ termeni) și aceasta este minimă din punct de vedere lexicografic.
• Dintre numerele din intervalul $[10,13]$, numerele $10$, $11$ și $13$ admit o descompunere cu un număr maxim de termeni ($3$ termeni), dar o descompunere maximală a lui $11$ ($1+2+8$) este minimă din punct de vedere lexicografic.
• În intervalul $[16,17]$ numerele admit câte două descompuneri maximale:
  • $16=1+3+12$;
  • $16=1+5+10$;
  • $17=1+2+14$;
  • $17=1+4+12$.
    Descompunerea minimă din punct de vedere lexicografic este $1+2+14$ și corespunde valorii $17$.