În al doilea rând, Laika vrea ca cadoul ei să aibă o semnificaţie specială. Au trecut exact $K$ zile de când a cunoscut-o pe Azusa şi ea vrea ca cadoul să indice acest lucru. De aceea Laika a aranjat toate mulţimile care satisfac condiţia explicată mai sus în ordine Laikană (explicată mai jos), obţinând astfel un şir infinit de mulţimi finite $S{~0~}, S{~1~}, ...$. Ea vrea să selecteze ca cadou mulţimea $S{~K~}$. Puteţi să o ajutaţi să îndeplinească această sarcină?

*Ordine Laikană.* Selectăm două mulţimi $A$ şi $B$. Atunci, $A$ apare înaintea lui $B$ în ordinea Laikană dacă şi numai dacă $max A < max B$, sau $max A = \max B$ şi $A - { max A }$ apare înaintea lui $B - { max B }$ în ordinea Laikană. În scopul acestei definiţii, fie $max {} = -infinit$. Observaţi că această ordine este întotdeauna bine definită pentru mulţimi finite de numere întregi pozitive.

*Ordine Laikană.* Selectăm două mulţimi $A$ şi $B$. Atunci, $A$ apare înaintea lui $B$ în ordinea Laikană dacă şi numai dacă $max A < max B$, sau $max A = max B$ şi $A - { max A }$ apare înaintea lui $B - { max B }$ în ordinea Laikană. În scopul acestei definiţii, fie $max {} = -infinit$. Observaţi că această ordine este întotdeauna bine definită pentru mulţimi finite de numere întregi pozitive.

h2. Date de intrare

h2. Restrictii
* $1 ≤ T ≤ 5$

* Pentru 8 puncte, $0 ≤ K ≤ 100$.
* Pentru 21 puncte, $0 ≤ K ≤ 1 000 000$.
* Pentru 41 puncte, $0 ≤ K ≤ 500 000 000$.
* Pentru 14 puncte, $0 ≤ K ≤ 1000 000 000$.
* Pentru 16 puncte, $0 ≤ K ≤ 1500 000 000$.

* Pentru 18 puncte, $0 ≤ K ≤ 100$.
* Pentru alte 18 puncte, $0 ≤ K ≤ 1 000 000$.
* Pentru alte 18 puncte, $0 ≤ K ≤ 500 000 000$.
* Pentru alte 18 puncte, $0 ≤ K ≤ 1000 000 000$.
* Pentru restul punctelor, $0 ≤ K ≤ 1500 000 000$.

h2. Exemple

1 1
1 2
2 1 2

1 3
| |4

1 3|
|4

5
6
100

h2. Explicatii

Observaţi că $S_0 = \emptyset, S_1 = \{1\}, S_2 = \{2\}, S_3 = \{1, 2\}, S_4 = \{3\}, S_5 = \{1, 3\}, S_6 = \{1, 2, 3\}, S_{100} = \{1, 2, 3, 7, 8\}, S_{1000} = \{1, 2, 3, 5, 10, 11, 12\}$. Acestea sunt exact mulţimile afişate în exemplu (împreună cu mărimile lor). Observaţi că $S_6 \neq \{2, 3\}$ --- deaorece $2, 3 \in \{2, 3\}$, dar $\gcd(2, 3) = 1 \not \in \{2, 3\}$.
 
\end{document}
 
Poveste şi cerinţă...
 
h2. Date de intrare
 
Fişierul de intrare $present.in$ ...
 
h2. Date de ieşire
 
În fişierul de ieşire $present.out$ ...
 
h2. Restricţii
 
* $... ≤ ... ≤ ...$
 
h2. Exemplu
 
table(example). |_. present.in |_. present.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

Observaţi că $S{~0~} = {}, S{~1~} = {1}, S{~2~} = {2}, S{~3~} = {1, 2}, S{~4~} = {3}, S{~5~} = {1, 3}, S{~6~} = {1, 2, 3}, S{~100~} = {1, 2, 3, 7, 8}, S{~1000~} = {1, 2, 3, 5, 10, 11, 12}$. Acestea sunt exact mulţimile afişate în exemplu (împreună cu mărimile lor). Observaţi că $S{~6~} != {2, 3}$, deaorece $2, 3$ apartin lui ${2, 3}$, dar $gcd(2, 3) = 1$ ce nu apartine lui ${2, 3}$.

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