Problem description
Jasio jest wielkim fizykiem. Właśnie odkrył ultrapiękne twierdzenie obalające połowę teorii fizyki. Oczywiście swoje twierdzenie musi poprzeć dowodami. Aby twierdzenie było prawdziwe, średnia wyniku z K doświadczeń powinna wynosić dokładnie $\frac{S}{K}$. Nieszczęśliwie jednak, po dokonaniu N pomiarów, każdy z wyników: 1, 2, 3, …, N, wystąpił dokładnie raz.
“To na pewno wina niedokładności pomiaru!” rzucił Jasio. Pomóż mu wybrać K pomiarów spośród N wykonanych, które pokaże na konferencji na dowód swojej tezy.
Napisz program, który: wczyta liczby N, S, K, wyznaczy które pomiary należy wybrać, aby dowieść tezy Jasia i wypisze wynik na standardowe wyjście.
Wejście
W pierwszym (i jedynym) wierszu wejścia znajdują się trzy liczby naturalne N, S, K, pooddzielane pojedynczymi odstępami.
Wyjście
Należy wypisać ciąg N
znaków (bez żadnych odstępów pomiędzy nimi). i-ty znak powinien być
1, jeśli należy uwzględnić wynik i-tego pomiaru, zaś 0 w
przeciwnym przypadku.
Jeśli nie istnieje sposób udowodnienia tezy Jasia (nie da się wybrać
K pomiarów, których średnia
wynosi $\frac{S}{K}$, należy wypisać na
wyjście jedno słowo NIE.
W przypadku, gdy istnieje wiele rozwiązań, wystarczy wypisać dowolne z nich.
Ograniczenia
1 ≤ K ≤ N ≤ 500 000, 1 ≤ S ≤ 1012.
Przykład
| Input | Output | Explanation |
|
|
Wystarczy wybrać pomiary 1, 2, 4. |
| Input | Output | Explanation |
|
|
Uzyskanie średniej $\frac{5}{3}$ trzech pomiarów jest niemożliwe. |
| Input | Output | |
|
|