Muguros

Prințișorul Mugurel din Imperiul Rațelor de Cauciuc a primit cadou la $12$ ani primul său interval de numere! Fiind un viitor informatician strălucit, a început să ia aleatoriu numere din interval și să le analizeze. El este interesat să descopere numerele muguriste.

Un număr natural $k$ se numes,te mugurist dacă, pentru două numere naturale $x$ și $y$ date, există două numere naturale $a$ și $b$ astfel încât $k = x^a + y^b \ (a, b \geq 0)$.

Pentru un număr $k$ mugurist, $x^a + y^b$ reprezintă scrierea muguristă a lui $k$, iar $x$ și $y$ reprezintă valorile de bază din scrierea muguristă.

Un interval $[l, r]$ se numește muguros dacă nu conține niciun număr mugurist.

Mugurel vrea să-și pună mintea la contribuție, așa că vrea să rezolve cele două probleme de antrenament din Gazeta Informaticii pentru Rățuște Începătoare:

1. Dându-se un număr $k$, determinați dacă acesta este un număr mugurist.
2. Dându-se două numere $l$ și $r$, determinați cel mai mare interval muguros $[t, w]$ care este inclus în $[l, r]$.

Ajutați-l pe Mugurel să facă primii pași spre o carieră de succes în informatică!

Date de intrare

Prima linie va conține un număr $C$, reprezentând tipul cerinței.
A doua linie va conține două numere $x$ și $y$, reprezentând valorile de bază în scrierea muguristă.
Dacă $C = 1$, atunci a treia linie va conține un singur număr întreg $k$, reprezentând numărul care trebuie verificat.
Dacă $C = 2$, atunci a treia linie va conține două numere întregi $l$ și $r$, separate printr-un spațiu, reprezentând intervalul în care se caută cel mai mare interval muguros.

Date de ieșire

Dacă $C = 1$, atunci prima linie va conține DA sau NU, reprezentând dacă numărul $k$ este sau nu mugurist.
Dacă $C = 2$, atunci prima linie va conține două numere $t$ și $w$, separate printr-un spațiu, reprezentând capetele celui mai mare interval muguros inclus în $[l, r]$. Dacă sunt mai multe astfel de intervale, se afișează cel cu $t$ minim.

Restricții și precizări

• $C \in {1, 2}$
• $0 \leq x, y \leq 10^9$
• $0 \leq k \leq 10^9$
• $0 \leq l \leq r \leq 10^9$
• Se consideră că $0^0 = 0$.
• Pentru $C = 2$, se garantează că există cel puțin un interval muguros de lungime cel puțin $1$.

Exemplul 1

muguros.in

1
3 2
25

muguros.out

DA

Explicație

În primul exemplu, numărul $25$ este mugurist deoarece se poate scrie ca $3^2 + 2^4$

Exemplul 2

muguros.in

1
3 2
16

muguros.out

NU

Explicație

În al doilea exemplu, nu există nicio pereche de numere naturale $(a, b)$ astfel încât $3^a + 2^b = 16$.

Exemplul 3

muguros.in

2
2 3
1 20

muguros.out

14 16

Explicație

În al treilea exemplu, singurul interval muguros de lungime maximă $(3)$ este $[14, 16]$.

Exemplul 4

muguros.in

2
3 5
21 39

muguros.out

21 25

Explicație

În al patrulea exemplu, există $2$ intervale muguroase de lungime maximă: $[21, 25], [35, 39]$. Cel cu capătul stâng de valoare minimă este $[21, 25]$.