Wstęp do programowania w C++

Jak w wielu krajach, również w Bajtocji mieszkańcy wymyślili swój narodowy deser: bajtogalaretę. Są to galaretki zanużone w budyniu. Przysmak jest jednak w fazie testów. Przygotowuje się go w pojemnikach o wymiarach a[dm] x b[dm] x 1 dm. Najpierw do formy wpuszcza się sześcienne galaretki o objętości 1 dm3 każda. Zatrzymują się one w różnych miejscach pojemnika, ale ich odległości od jego dna oraz brzegów wyrażone w decymetrach są zawsze liczbami całkowitymi (specjalna receptura). Następnie od góry zalewa się je budyniem. Ten oczywiście ścieka na dół formy, gdy jednak spotyka na swojej drodze galaretkę, to połowa płynie na lewą stronę, a połowa na prawą. Gdy budyń nie mieści się z jednej strony, to przepływa na drugą. Jako że formy są szybko schładzane, nie działa tu zasada naczyń połączonych. Kucharze pracują jeszcze nad optymalną gęstością bajtogalarety i chcieliby prowadzić statystyki mówiące o tym, ile budyniu zajduje się w każdej kolumnie o szerokości 1 dm. Pomóż im i napisz program, który po prześwietleniu formy odpowie na ich pytanie.

Input

Na początku zostaną podane 4 liczby całkowite: a i b (a,b<=100) oznaczające wymiary formy, w (0<w<=a) mówiąca, na którym decymetrze od lewej strony znajduje się wlew budyniu oraz l oznaczająca ilość budyniu do dyspozycji w dm3.

Następnie do wczytania będzie b wierszy po a znaków "0" lub "1" oznaczających kolejno miejsce puste lub wypełnione galaretą. W każdym przypadku testowym budyń mieści się w pojemniku.

Output

Na wyjściu wypisz a liczb rzeczywistych odpowiadających ilości budyniu w każdej kolumnie pojemnika.

Example

Input:
14 8 6 22
00000000000000
01010110000000
01010100000000
00111101100000
10000101000000
00000111010000
01000001001010
00000001001000


Output:
1 1 3 1 3 1 3 0 2.5 2 0 2 1 1.5