Number Guessing Game

Time limit3sMemory limit512 MB

Summary

For each N from 1 to M, find the first questions student 1 can ask to maximize their own winning chance, given K students playing the guessing game.

Level: Medium7 of 10
Topics: Game theory, Dynamic programming, Probability
Solved: No attempts yet

Problem

$K$ students play a game to guess a number the teacher picks.

The teacher picks a random integer $X$ from 1 to $N$ inclusive. The students know $N$ in advance.
Starting with student 1 and going one at a time, each student picks a number $Y$ from 1 to $N$ and asks about it. If $X=Y$ , that student wins. Otherwise, the teacher reveals to all students whether $Y$ is less than or greater than $X$ .
After student $K$ asks, the turn returns to student 1. The game continues until some student guesses $X$ .

Each student asks the question that maximizes their own probability of winning. If several such questions exist, the student picks one of them uniformly at random. All students know that everyone uses this strategy.

Your goal is to find the candidates for the first question student 1 can ask on the first turn.

Given a positive integer $M$ and the number of students $K$ , write a program that, for each $N = 1, 2, \ldots, M$ , finds the candidates for student 1's first question.

Input

The first line contains a positive integer $M$ ( $2 \le M \le 200$ ).

The second line contains the number of students $K$ ( $2 \le K \le 50$ ).

Output

Print $M$ lines. On line $i$ , for $N = i$ , let $P_1, P_2, \ldots, P_k$ be the candidate answers for student 1's first question in ascending order. Print $k+1$ numbers separated by spaces in the form $k P_1 P_2 \ldots P_k$ .

Examples2

Example 1
Input
```
4
3
```
Expected output
```
1 1
2 1 2
3 1 2 3
2 1 4
```

Example 2

Input

15
5

Expected output

1 1
2 1 2
3 1 2 3
4 1 2 3 4
5 1 2 3 4 5
2 1 6
2 1 7
2 1 8
2 1 9
2 2 9
2 3 9
2 4 9
2 6 8
2 1 14
1 8