Tournament Triple Paradox

In the JOI Kingdom, a table tennis tournament is held among N beavers numbered from 1 to N. They play a round‐robin tournament (each pair of beavers competes exactly once) with no draws. Bitaro claims that there are exactly M choices of 3 beavers that form a triple paradox. Three beavers i, j, k (with 1 ≤ i < j < k ≤ N) form a triple paradox if and only if

(1) beaver i beats beaver j, beaver j beats beaver k, and beaver k beats beaver i; or
(2) beaver i beats beaver k, beaver k beats beaver j, and beaver j beats beaver i.

Since you are not sure whether Bitaro’s information is correct, you have decided to determine whether there exists any tournament result consistent with his information. If it exists, output any one such tournament result; otherwise, output −1.

Output Format: If a valid tournament exists, output N lines. The i-th line (1-indexed) must be a string of length N where the j-th character is:

• '1' if beaver i wins against beaver j,
• '0' if beaver i loses to beaver j, and
• '-' if i = j.

If no tournament satisfies the conditions, output only -1.

Note on 3‐cycles: Every triple of distinct beavers results in either a transitive triple or a cycle (the triple paradox). In a transitive tournament (where beaver i beats j for every i < j), the number of triple paradoxes is 0. In a "regular" tournament (one that is almost balanced), the maximum possible number of triple paradoxes is achieved. It can be shown that the maximum number is \[ \begin{cases} \frac{N^3-N}{24} &\text{if } N \text{ is odd},\\[6pt] \frac{N(N^2-4)}{24} &\text{if } N \text{ is even}. \end{cases} \]

inputFormat

The input consists of a single line containing two integers N and M:

• N (the number of beavers, 1 ≤ N ≤ (a reasonable bound))
• M (the claimed number of triple paradoxes)

You may assume that 0 ≤ M ≤ maximum possible triple paradoxes (as defined above).

outputFormat

If there exists a tournament result with exactly M triple paradoxes, then output N lines representing the tournament result. The i-th line must be a string of length N where the j-th character is:

• '1' if beaver i wins against beaver j,
• '0' if beaver i loses to beaver j, and
• '-' if i = j.

If no such tournament exists, output a single line with -1.

sample

3 1

1

The output should be a 3x3 tournament matrix that yields exactly 1 triple paradox. One possible valid output is:
-01
1-0
10-</code></pre>