S is one of the few science and engineering geniuses at school. The two-legged electric balance bike, the electrode device that controls body movement by stimulating the motor nerves of the upper arms, waist, and thighs, and the massive, lightweight, flexible screen that can be lifted by a drone are just the tip of the iceberg of S's peak technical prowess. This time, S has set her sights on the recently popular Large Language Models (LLM).

Large Language Models are an emerging direction in machine learning, characterized by the use of massive corpora to train language models, and it is the development of algorithms and the improvement of computing power that have made training large language models no longer a struggle. Furthermore, some of the latest large language models support not only text input and output but also multimodal input and output in formats such as audio, images, and video. However, S discovered that even multimodal large language models cannot correctly process a special type of image—Random Dot Stereograms.

A stereogram is an image that uses optical illusions to create a sense of depth, and the principle of a random dot stereogram is to produce stereoscopic vision by applying a translation transformation to a randomly generated bitmap. The image below is a simple random dot stereogram. By shifting the part within the green dashed box to the left by $2$ pixels, the effect of the part within the dashed box floating above the original image can be produced. Note that except for the parts covered by the dashed box and the red rectangle to the left of the dashed box in the left image, and the green rectangle to the right of the dashed box in the right image, the peripheral parts of the image must remain exactly the same, while the areas covered by the red and green rectangles can be generated randomly. Formally, if we denote the left image as $W$ and the right image as $Y$, then when shifting the rectangular sub-region from rows $r_1$ to $r_2$ and columns $c_1$ to $c_2$ in $W$ to rows $r_1$ to $r_2$ and columns $c_1'$ to $c_2'$ in $Y$, it must satisfy $r_1\le r_2$, $c_2 - c_1 = c_2'-c_1'\ge 0$ (when it is $0$, only one column is moved), and $c_1>c_1'$. Only the pixels in rows $r_1$ to $r_2$ and columns $c_1'$ to $(c_1-1)$ in $W$, and rows $r_1$ to $r_2$ and columns $(c_2'+1)$ to $c_2$ in $Y$ can be generated independently and randomly, regardless of whether the rectangular regions overlap before or after the translation.

S discovered that although large language models can recognize traditional image CAPTCHAs, if random dot stereograms are used to generate CAPTCHAs, the large language models will be unable to recognize them correctly! To verify this discovery, S needs to generate different random dot stereograms to test whether large language models can recognize image content. As the first step of the plan, S wants to test whether large language models can perceive rectangles in images. Specifically, S will input two $N \times M$ bitmaps $W$ and $Y$, which can be represented as $01$ matrices, into the large language model and ask whether $Y$ can be obtained by shifting a rectangular sub-region of $W$ to the left. Assume that before and after the translation, this rectangular sub-region does not exceed the boundaries of the original images. To verify the output of the large language model, S needs a program to calculate, for all possible translation distances, whether the right-side image $Y$ can be obtained by shifting a rectangular sub-region of the left-side image $W$, and if feasible, find the maximum area of such a rectangular sub-region. Since S has to accompany M shopping this weekend, she would like to ask you to help her implement this program.

Input

The input is read from standard input.

The first line contains two positive integers $N, M$, representing the number of rows and columns of the two pixel matrices. It is guaranteed that $1\le N, M\le 500$.

The next $N$ lines each contain a string of $M$ characters, representing each row of $W$. It is guaranteed that each character is 0 or 1.

The next $N$ lines each contain a string of $M$ characters, representing each row of $Y$. It is guaranteed that each character is 0 or 1.

Output

Output to standard output.

Output a single line containing $(M-1)$ integers separated by single spaces, where the $i$-th ($1\le i \le M - 1$) integer represents the maximum area of a possible rectangular sub-region when the translation distance is $i$ pixels. If no rectangular sub-region satisfies the requirements, output -1 for that translation distance.

Examples

Input 1

4 4
0100
0110
1001
1000
0100
1100
0011
0000

Output 1

9 4 -1

Note 1

When the translation distance is fixed at $1$, the maximum possible rectangular sub-region corresponds to the rectangle from row $2$ to row $4$ and column $2$ to column $4$ in $W$, which after translation corresponds to row $2$ to row $4$ and column $1$ to column $3$ in $Y$.

If we assume the translation distance is $2$, the maximum possible rectangular sub-region is the rectangle corresponding to the entire $3$rd column in $W$.

It can be proven that there is no translation method for a translation distance of $3$.

Input 2

See ex_2.in and ex_2.ans in the download directory.

Note 2

This example is the image attached to the problem statement.

Subtasks

For all data, it is guaranteed that $1\le N, M\le 500$, and the input $W$ and $Y$ are $N \times M$ character matrices containing only 0 and 1.

Note