Trey Frey - Refresh

⠀

A permutation$$$^{\text{∗}}$$$ of length $$$n$$$ is called valid if it has both of the following properties:

It is bitonic$$$^{\dagger}$$$;
Exactly $$$m$$$ of its subsets are cycles$$$^{\ddagger}$$$.

Let $$$k$$$ denote the number of permutations satisfying the above condition. Your task is to find and print $$$\min(k, 2000)$$$ examples of such permutations.

$$$^{\dagger}$$$ A permutation $$$p_1, p_2, \ldots, p_n$$$ is bitonic if there exists an index $$$i$$$ ($$$1 \leq i \leq n$$$) such that

$$$p_{j-1} \leq p_j$$$ for $$$2 \leq j \leq i$$$;
$$$p_j \geq p_{j+1}$$$ for $$$i \leq j \leq n-1$$$.

$$$^{\ddagger}$$$ A subset $$$C \subseteq \{ 1, 2, \ldots, n \}$$$ is a cycle if it satisfies the following conditions:

$$$C$$$ is non-empty;
if $$$x \in C$$$, then $$$p_x \in C$$$;
$$$C$$$ is minimal, i.e., there does not exist a cycle $$$C'$$$ such that $$$C' \subset C$$$.

$$$^{\text{∗}}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input

The input consists of a single line containing two integers $$$n$$$, $$$m$$$ ($$$1 \le m \leq n \le 100$$$) — the length of the permutations and the target number of cycles.

Output

In the first line, print a single integer $$$r$$$: the number of permutations you are going to print. Note that $$$r$$$ must be $$$\min(k, 2000)$$$ as defined in the statement.

Then, print $$$r$$$ lines. Each line must contain a bitonic permutation of length $$$n$$$, with $$$m$$$ cycles.

Note

In the example, there are $$$9$$$ valid permutations (i.e., bitonic permutations of length $$$6$$$, with $$$3$$$ cycles). For example, $$$[3, 5, 6, 4, 2, 1]$$$ is bitonic (in the above definition, $$$i = 3$$$), and it has $$$3$$$ cycles: $$$\{1, 3, 6\}$$$, $$$\{2, 5\}$$$, $$$\{4\}$$$. So you have to print $$$r = \min(9, 2000) = 9$$$ such permutations.

Keygen 3

Examples