H. Keygen 3
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
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.

Example
Input
6 3
Output
9
1 4 5 6 3 2
6 5 4 3 2 1
1 2 4 5 6 3
1 2 5 6 4 3
1 3 4 6 5 2
1 5 6 4 3 2
3 5 6 4 2 1
1 3 6 5 4 2
2 6 5 4 3 1
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.