시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 0 0 0 0.000%

문제

Famous painter Quasimir Malevich painted a picture called “Black-and-white square”. The picture looks like a rectangle ﬁlled with black and white cells.

Art historian Erik Stripeson put forward a hypothesis that Quasimir painted the picture in the following way: he took a canvas that was initially white, and drew horizontal and vertical black stripes, one cell wide, from the edge to the edge of the canvas.

Association of Computational Art Studies wants to ﬁnd out whether this hypothesis can be correct. If it can be correct, they also want to know the minimal number of stripes that the painter had to draw in order to paint this picture. Moreover, they need to ﬁnd a way to draw this picture using this number of stripes.

입력

The ﬁrst line of the input ﬁle contains two integers h and w (1 ≤ h,w ≤ 50) — the height and the width of the picture.

Each of the next h lines contains w space-separated numbers. Number 0 denotes a white cell, number 1 denotes a black cell.

출력

If Stripeson’s hypothesis can’t be correct, output only the number -1.

If the hypothesis can be correct, the ﬁrst line of the output ﬁle should contain number n — the minimal possible number of stripes needed to draw the picture.

The second line should contain n numbers that describe a way to draw the picture using n stripes. A positive number x stands for drawing a vertical black stripe in x-th column (columns are numbered from left to right, starting with 1). A negative number -x stands for drawing a horizontal black stripe in x-th row (rows are numbered from top to bottom, starting with 1).

If there are several ways to draw the picture using n stripes, output any one of these ways.

예제 입력

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


예제 출력

4
1 3 -2 -3


예제 입력 2

2 2
1 0
0 0


예제 출력 2

-1


힌트

Tests with answer -1 (with numbers from 23 to 27) will be scored only if your solution passes at least one test with number from 12 to 22.