bile

Presupunem că avem două cutii notate $A$ și $B$. Cutia $A$ conține $N$ bile numerotate cu numerele naturale distincte: $0, 1, 2, \dots N-1$. Cutia $B$ este goală.

Spunem că o bilă dintr-o cutie este bila specială a acestei cutii dacă numarul $X$ cu care este numerotată aceasta bilă este egal cu media aritmetică a numerelor celorlalte bile din cutie.

La un moment dat, cineva mută bila cu numărul $K$ din cutia $A$ în cutia $B$.

Vi se cere să alegeți alte $K$ bile, din cutia $A$, pe care să le mutați în cutia $B$ astfel în cutia $B$ astfel încât cutia $B$ să conțină $K + 1$ bile, iar bila cu numărul $K$ să fie bila specială a cutiei $B$.

Cerință

Scrieți un program care citește numerele $N$ și $K$, apoi determină:

1. dacă, înainte să fie mutate bile din cutia $A$ în cutia $B$, există o bilă specială în cutia $A$; în caz afirmativ, programul determină numărul $X$ cu care este numerotată această bilă specială.
2. cel mai mic (în sens lexicografic) șir strict crescător al numerelor celor $K$ bile care pot fi mutate din cutia $A$ în cutia $B$ astfel încât cu numărul $K$ să fie bila specială a cutiei $B$.
3. cel mai mare (în sens lexicografic) șir strict crescător al numerelor celor $K$ bile care pot fi mutate din cutia $A$ în cutia $B$ astfel încât bila cu numărul $K$ să fie bila specială a cutiei $B$.

Date de intrare

Fișierul de intrare bile.in conține pe prima linie trei numere naturale $C, N$ și $K$, separate prin câte un spațiu. $C$ reprezintă cerința care trebuia rezolvată (1, 2 sau 3), iar $N$ și $K$ au semnificația din enunț.

Date de ieșire

Fișierul de ieșire bile.out va conține:

• dacă $C = 1$, pe prima linie, numărul natural $X$ reprezentând numărul bilei speciale din cutia $A$ sau valoarea $-1$ dacă cutia $A$ nu conține o astfel de bilă (reprezentând răspunsul la cerința 1);
• dacă $C = 2$, pe prima linie, un șir crescător de $K$ numere naturale, separate prin câte un spațiu (reprezentând răspunsul la cerința 2);
• dacă $C = 3$, pe prima linie, un șir crescător de $K$ numere naturale, separate prin câte un spațiu (reprezentând răspunsul la cerința 3);

Restricții și precizări

• $N$ număr natural, $4 \leq N \leq 100 \ 000$
• $K$ un număr natural $2 \leq K \leq \frac{N}{2}$
• Șirul $y_1, y_2, \dots y_k$ este mai mic în sens lexicografic decât șirul $z_1, z_2, \dots z_k$ dacă există un indice $p$, $1 \leq p \leq K$, astfel încat: $y_1 = z_1, y_2 = z_2, \dots y_{p-1} = z_{p-1}$ și $y_p < z_p$
• Pentru cerința 1 se acordă 20p, iar pentru fiecare dintre cerințele 2 și 3 se acordă câte 40p.

Exemplul 1

bile.in

1 9 3

bile.out

4

Explicație

Se rezolvă cerința 1.
$N = 9$.
Avem 9 bile inscripționate cu $0, 1, 2, 3, 4, 5, 6, 7, 8$.
Bilă specială este $X = 4$ deoarece:
$X = \frac{(0 + 1 + 2 + 3 + 5 + 6 + 7 + 8)}{8} = \frac{32}{8} = 4$.

Exemplul 2

bile.in

1 8 3

bile.out

-1

Explicație

Se rezolvă cerința 1.
$N = 8$.
Se va scrie în fișierul de ieșire valoarea $-1$ deoarece cutia $A$ nu conține nicio bilă specială.

Exemplul 3

bile.in

2 8 3

bile.out

0 2 7

Explicație

Se rezolvă cerința 2.
$N = 8$.
Șirurile strict crescătoare ale numerelor bilelor care pot fi mutate în cutia $B$, lângă bila specială $K = 3$, sunt: $0, 2, 7$ sau $0, 4, 5$ sau $1, 2, 6$, deoarece:
$3 = \frac{(0 + 2 + 7)}{3} = \frac{(0 + 4 + 5)}{3} = \frac{(1 + 2 + 6)}{3}$
Cel mai mic șir în sens lexicografic, crescător, este $0, 2, 7$.

Exemplul 4

bile.in

3 8 3

bile.out

1 2 6

Explicație

Se rezolvă cerința 3.
$N = 8$.
ecială.

Șirurile strict crescătoare ale numerelor bilelor care pot fi mutate în cutia $B$, lângă bila specială $K = 3$, sunt: $0, 2, 7$ sau $0, 4, 5$ sau $1, 2, 6$, deoarece:
$3 = \frac{(0 + 2 + 7)}{3} = \frac{(0 + 4 + 5)}{3} = \frac{(1 + 2 + 6)}{3}$
Cel mai mare șir în sens lexicografic, crescător, este $1 2 6$.