Problem Description

An $n \times m$ character matrix $a_{ij}$ is called a valid expression matrix if and only if it satisfies the following conditions.

• The matrix contains only the characters '1', '+', and '*'.

• The string formed by each row from left to right is a valid expression.

• The string formed by each column from top to bottom is a valid expression.

The weight of a valid expression matrix is defined as follows: evaluate all $n + m$ expressions formed by each row (left to right) and each column (top to bottom), and take the sum of their values.

Find, among all valid $n \times m$ expression matrices, one with the minimum weight. If there are multiple minimum answers, you may output any one of them.

We define a string $s$ to be a valid expression as follows.

• If $s = \overbrace{111\dots111}^{\text{at least one }1}$, then $s$ is a valid expression.

• If both $s$ and $t$ are valid expressions, then $s$ * $t$ is also a valid expression.

• If both $s$ and $t$ are valid expressions, then $s$ + $t$ is also a valid expression.

Input Format

The input consists of one line with two integers $n, m$ ($3 \leq n, m \leq 9$), separated by a space, representing the number of rows and columns of the matrix.

Output Format

Output $n$ lines, each containing $m$ characters. The $j$-th character of the $i$-th line is $a_{ij}$, representing a matrix with the minimum weight.

If there are multiple minimum answers, you may output any one of them.

4 4

1111
1*11
11*1
1111

Hint

For the sample, the weight of the matrix is $4488$. It can be proven that there is no matrix with a smaller weight.

Translated by ChatGPT 5