K. Keygen 3
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Luke has just discovered a new 5D kart videogame. However, the software is not free: in order to activate it, you need to provide a license key.

Luke has found out that, in order to be valid, a license key must be a permutation of length $$$n$$$ with both of the following properties:

  • it is bitonic;
  • it has $$$m$$$ cycles.

Let $$$k$$$ denote the number of license keys (i.e., the number of permutations satisfying the above conditions). Luke is an altruistic hacker, so he wants to provide distinct license keys for all his $$$2000$$$ friends. However, $$$k$$$ might be less than $$$2000$$$.

Help Luke by printing $$$r = \min(k, 2000)$$$ distinct valid license keys.

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).

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$$$.

A cycle is a subset $$$C \subseteq \{ 1, 2, \ldots, n \}$$$ such that

  • $$$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' \subsetneq C$$$.
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. The permutations must be distinct.

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

Explanation of sample 1. In the example, there are $$$9$$$ valid license keys (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.