Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.

Мали Перица је решио да обиђе Србију и посебно је заинтересован за обилазак водопада широм земље. Када је био на Гостиљским водопадима, покушао је да процени ток воде на дну водопада.


Као што сви знамо, водопад има висину \(h\) метара и ширину \(n\) метара. Водопад је такође са леве и десне стране ограничен ивицама тако да вода никада не отиче лево и десно од његових граница. Још једна занимљива ствар је што водопад може имати стене које ће преусмеравати ток воде. Наиме, ако вертикални млаз воде наиђе на стену, сав њен ток се дели на два дела тако да један део отиче на десно а други на лево. Уколико се стена налази уз леву или десну границу водопада, тада се сав ток воде преусмерава на једну страну. Више стена се може налазити једна поред друге и у том случају се вода преусмерава само на крај и почетак целог низа стена. Гарантује се да ће у свакој висини водопада постојати бар једно место које нема стену тако да је води гарантован пролаз на доле.


Формално, водопад можемо представити бинарном матрицом \(h \times n\), у којој је свако поље или проходно или се ту налази стена. Редови се индексирају почевши од 1, тако да је први ред на врху матрице, а \(h\)-ти ред на дну. Проток воде има вредност 1 на врху сваке колоне. Вода се у свакој колони спушта низ матрицу, све док не наиђе на стену. Уколико наиђе на стену, сав проток се дели на два целобројна дела и половина иде на леву страну а друга половина на десну страну. Уколико је проток непаран, тада преостала јединица иде лево или десно по следећем правилу:


Ако се више узастопних нула налази у реду матрице (више узастопних стена), тада се укупан проток изнад блока узастопних нула дели на два дела и једна половина преусмерава на прво место лево од блока а друга на десно. Правило за преосталу јединицу протока је исто као и малопре - ако је ред непаран вишак иде лево од блока, а ако је паран десно. Ако се стена или блок стена налази уз леву или десну ивицу матрице, сав проток изнад стене или блока се усмерава на супротну страну. Гарантовано је да неће постојати ред матрице који садржи само нуле.


Перица вам је дао матрицу која представљаја изглед једног водопада. Ваш задатак је да одредите проток воде на свим местима на његовом дну.

Опис улаза

У првом реду стандардног улаза налазе се два броја \(h\) и \(n\), који представљају висину и ширину матрице, респективно. У сваком од наредних \(h\) редова налази се по \(n\) бројева из скупа \(\{0, 1\}\), при чему \(0\) означава да се на одговарајућем пољу налази стена, док \(1\) представља проходно поље.

Опис излаза

У једином реду стандардног излаза потребно је исписати \(n\) бројева - вредност тока на дну сваке од колона матрице.

Пример 1

Улаз

3 3
1 1 0
1 0 1
0 1 1

Излаз

0 2 1

Пример 2

Улаз

3 3
0 1 0
1 0 1
1 1 0

Излаз

1 2 0

Пример 3

Улаз

4 5
1 0 1 0 1
1 1 0 0 1
0 1 1 1 0
1 0 1 0 1

Излаз

1 0 3 0 1

Пример 4

Улаз

5 7
1 1 1 1 0 0 0
1 0 1 0 1 0 1
1 1 0 0 0 1 0
1 0 0 1 1 0 1
0 1 1 0 1 1 0

Излаз

0 2 1 0 2 2 0

Пример 5

Улаз

1 3
1 0 1

Излаз

2 0 1

Објашњење примера

У првом примеру, после првог реда, протоци имају вредности \([1, 2, 0]\), јер се вода из треће колоне преусмерава на лево због тога што је ту стена уз десну ивицу. Након другог реда, протоци су \([2, 0, 1]\), јер се две јединице протока из средње колоне деле на два дела. Коначно, проток на крају трећег реда је \([0, 2, 1]\), јер се ток уз ивицу преусмерава на супротну страну.

У другом примеру, протоци на крају редова су:

0 3 0
1 0 2
1 2 0

У трећем примеру протоци на крају редова су:

2 0 2 0 1
2 1 0 0 2
0 3 0 2 0
1 0 3 0 1

У четвртом примеру, протоци на крају редова су:

1 1 1 4 0 0 0
1 0 4 0 2 0 0
1 3 0 0 0 3 0
2 0 0 2 1 0 2
0 2 1 0 2 2 0

У петом примеру постоји само један ред, на чијој се средини налази стена. Пошто је у питању непаран ред, ток из средине се преусмерава на лево.

Ограничења

Тест примери су подељени у 5 дисјунктних група: