A m-cycle in a directed graph is defined to be a sequence of vertices v₀-v₁-v₂-v₃-...-v_m where an edge (v_i, v_i+1) exists for each 0 <= i < n, v_i != v_j for all 0 <= i < j < m and v_m = v₀. For a given graph of n vertices we can count the number of cycles in it. Now you task is a little harder: find the maximum value among all graphs with certain constraints, that is, your graph should contain an edge from either vertex x to y or y to x, but not both.
Assume there are R m-cycles in your output, your solution will be awarded by w * R points, where w is related to n and m. Your score will be the sum of scores of all test cases. Note your source must not be larger than 10000 bytes.

Input

One line containing two blank-separated integers, n and m, where 3 <= m <= n <= 17.

Output

Adjacent matrix A of the graph you found. Numbers must be separated by spaces. Edge (i, j) exists when and only when A_ij = 1. A_ij + A_ji <= 1 and A_ii = 0 for any 0 <= i, j < n, or your solution will be judged as wrong answer.

Example

Input:
3 3

Output:
0 0 1
1 0 0
0 1 0

Assume w = 0.2, this solution will get 0.2 * 1 = 0.2 points for this case.