Contest problemset description

Kenarf i Kenaj przygotowali N zadań na tegoroczne warsztaty przygotowujące do II etapu Bitockiej Olimpiady Informatycznej Juniorów. Każdemu z zadań przyporządkowali jako trudności liczby całkowite t₁, …, t_N. Jednakże, okazało się, że przygotowali o K za dużo zadań, zatem z niektórych z nich chcieliby zrezygnować. Chcieliby wybrać K zadań, których się pozbędą, w taki sposób, żeby różnica między najtrudniejszym, a najłatwiejszym zadaniem, które zostaną, była najmniejsza możliwa.

Obaj panowie są bardzo zarobieni przygotowywaniem paczek, dlatego poprosili Ciebie, żebyś pomógł im wybrać zadania.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite N oraz K oznaczające odpowiednio liczbę zadań oraz liczbę zadań, z których należy zrezygnować. W następnym wierszu następuje ciąg N liczb całkowitych t₁, …, t_N, gdzie t_i oznacza trudność i-tego zadania.

Wyjście

W pierwszym i jedynym wierszu wyjścia należy wypisać jedną liczbę, oznaczającą najmniejszą możliwą różnicę między najtrudniejszym a najprostszym zadaniem, po zrezygnowaniu z pewnych K zadań.

Ograniczenia

1 ≤ N ≤ 1 000 000, 0 ≤ K < N, 1 ≤ t_i ≤ 10⁹.

Podzadania

Przykład

7 1
3 7 1 3 8 2 10

7

Wielki wyświetlacz, przygotowany przez komitet główny Bitockiej Olimpiady Informatycznej Juniorów (ten sam, co w zadaniu Zepsuty wyświetlacz), jest bardziej wadliwy, niż początkowo przypuszczano. Nie dość, że źle prezentuje wyniki podzielne przez pewną liczbę, to w dodatku resetowanie go jest niesamowitą udręką! Za każdym razem, aby zmienić to, co w danym momencie się wyświetla, należy najpierw wyczyścić całą matrycę, a dopiero później rysować to, co powinno być w tym momencie wyświetlane.

Wyświetlacz składa się z matrycy N × N pikseli. Każdy piksel może przybrać dwa kolory, biały (oznaczony znakiem kropki .) lub czarny (oznaczone znakiem krzyżyka #). Resetowanie wyświetlacza polega na zmianie wszystkich pikseli tak, żeby były czarne. Jednakże, nie da się tego osiągnąć w bezpośredni sposób. Jedyna możliwość, żeby zmienić to, jak aktualnie świecą się piksele, jest wybranie pewnego wiersza pikseli oraz pewnej kolumny, a następnie przerysowanie tego wiersza w danej kolumnie. Rozważmy poniższy przykład wyświetlacza rozmiaru 3 × 3:

.##
#.#
#..

W tej sytuacji, gdybyśmy wybrali trzeci wiersz, po czym przerysowali go w kolumnie pierwszej, wyświetlacz zmieniłby swój stan do poniższego:

###
..#
...

Gdyby teraz wybrać pierwszy wiersz, a następnie przerysować go w każdej z kolumn, otrzymalibyśmy wyświetlacz cały ustawiony na czarno:

###    ###    ###    ###
..# -> #.# -> ### -> ###
...    #..    ##.    ###

Okazuje się, że za czyszczenie wyświetlacza (30 razy w każdej sekundzie!) odpowiedzialny jest krasnal Bitek, ukryty pod podłogą sali zawodów (podobnie, jak krasnale sterujące światłami drogowymi, które, jak każdy wie, są ukryte pod jezdnią). Krasnal Bitek ledwo daje radę i bardzo przydałby mu się program, który pomoże mu w czyszczeniu wyświetlacza. Pomóż mu i napisz program, który policzy, ile razy Bitek musi wykonać operację przerysowania, żeby zmienić kolor wszystkich pikseli na czarny.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N oznaczająca wymiary wyświetlacza. W następnych N wierszach następuje opis początkowego stanu wyświetlacza, i-ty wiersz składa się z N znaków kropki . lub krzyżyka #, j-ty znak opisuje stan j-tego piksela w i-tym wierszu.

Wyjście

W pierwszym i jedynym wierszu wyjścia należy wypisać jedną liczbę całkowitą, oznaczającą minimalną liczbę operacji, która wystarczy, aby wszystkie piksele miały czarny kolor, lub -1, jeżeli nie jest to możliwe.

Ograniczenia

1 ≤ N ≤ 1 000.

Podzadania

Przykład

3
.##
#.#
#..

4

6
.....#
#..#.#
....#.
#..#.#
...##.
.#....

9

2
..
..

-1

Dawno, dawno temu, za 111 górami i 111 lasami, w XIV liceum ogólnomagicznym odbywały się warsztaty przygotowujące do II etapu Bajtockiej Olimpiady Bitów i Charów. Na straży szkoły stał Hory Portier, chroniący uczniów przed nadchodzącymi potworami. Do walki z potworami wykorzystuje wyroby magiczne, oferowane mu przez Serwerusa Skype’a.

Hory Portier potrafi zaglądać w przyszłość (dzięki lekcjom z nikim innym jak jedynym Wróżbitą Maciejem), zatem ma dostępny ciąg zdarzeń, które zajdą w przyszłości. Zdarzenia ułożone są chronologicznie od 1 do N-tego. Każde ze zdarzeń jest jednego z dwóch typów:

• Do szkoły podchodzi potwór rodzaju p,
• Serwerus Skype oferuje Horemu Portierowi miksturę rodzaju p, którą Hory Portier może przyjąć lub nie.

Hory Portier doskonale zdaje sobie sprawę, że do walki z potworem rodzaju p wystarczy mu dokładnie jedna mikstura tego samego rodzaju, którą zużywa w trakcie walki. Z drugiej strony, wszystkie mikstury przechowuje w swojej Kanciapie Tajemnic, której to pojemność jest ograniczona. Nie chciałby zatem przechowywać mikstur, które mogłyby okazać się nieprzydatne. Innymi słowy, załóżmy, że w momencie, w którym Hory Portier przechowuje w swojej Kanciapie najwięcej mikstur, jest ich dokładnie K. Hory Portier chciałby, żeby wśród wszystkich możliwych strategii przyjmowania mikstur wybrać taką, że K jest możliwe najmniejsze.

Hory Portier potrafi czarować, ale nie programować, zatem poprosił Cię o pomoc! Mając listę przyszłych wydarzeń oblicz, jaki jest minimalny rozmiar Kanciapy Tajemnic, aby Hory Portier zawsze miał dostępną miksturę przed walką z potworem oraz które z mikstur powinien przyjąć od Serwerusa Skype’a.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N oznaczająca liczbę przyszłych wydarzeń. W następnych N wierszach następuje opis kolejnych zdarzeń, i-te zdarzenie opisane jest przez jeden znak oraz jedną liczbę c_i, p_i. Jeżeli c_i jest równe ! to oznacza, że Hory Portier musi w tym momencie walczyć z potworem typu p_i. Jeżeli c_i jest równe +, to oznacza, że Serwerus Skype oferuje Horemu Portierowi miksturę na potwory rodzaju p_i.

Wyjście

W pierwszym wierszu wyjścia należy wypisać jedną liczbę całkowitą K oznaczającą minimalny potrzebny rozmiar Kanciapy Tajemnic lub jedną liczbę  − 1, jeżeli niemożliwe jest wygranie ze wszystkimi potworami. Jeżeli K ≥ 0, w drugim wierszu należy wypisać ciąg liczb równych 0 lub 1, oznaczający, które z kolejnych mikstur Hory Portier przyjmuje od przez Serwerusa Skype’a według kolejności wydarzeń typu + na wejściu (0 oznacza nieprzyjęcie, a 1 przyjęcie mikstury). Jeżeli istnieje wiele możliwości, należy wpisać dowolne z nich.

Ograniczenia

1 ≤ N ≤ 200 000, 1 ≤ p_i ≤ N.

Podzadania

W każdym zestawie testowym otrzymasz 50% punktów jeżeli pierwszy wiersz wyjścia będzie poprawny.

Przykład

14
+ 2
+ 1
+ 1
+ 2
+ 4
+ 3
! 1
! 3
+ 4
! 2
+ 2
! 2
! 4
! 1

4
0 1 1 1 0 1 1 1 

3
+ 2
! 1
+ 1

-1