405003: GYM101736 C Cakes

C. Cakestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Our friend, the little Cactus, has n stacks of cakes and an integer k. Initially, the n stacks of cakes have sizes 1, 2, ..., n, that is the ith stack has i cakes. For aesthetic reasons, Cactus wants to make a large stack of cakes. Cactus can perform up to 10⁵ operations on the n stacks.

Let s_i denote the size of the ith stack. Each operation consists of 3 steps.

1. Cactus chooses an integer a where 2 ≤ a ≤ k.
2. Cactus chooses two stacks A and B, where s_A ≥ (a - 1)·s_B.
3. Cactus moves (a - 1)·s_B cakes from stack A to stack B.

Now Cactus wants to know the size of the largest possible stack he could make. However, Cactus likes surprises, so he wants you to tell him the operations he should perform to make the largest possible stack. Input

The first line contains two space separated integers n and k (1 ≤ n ≤ 200, 2 ≤ k ≤ 12).

Output

In the first line, output a single integer x representing the number of operations Cactus should perform.

For each of the next x lines, output two space separated integers y_i, z_i, and t_i, representing an operation where Cactus should choose the integer t_i, and move cakes from stack y_i to stack z_i.

Your solution will be considered correct if 0 ≤ x ≤ 10⁵, each operation is valid, and the largest possible stack that could be made this way is one of the n stacks after performing all the operations.

If there are multiple solutions, output any of them.

ExampleInput

6 3

Output

7
6 3 3
4 2 3
3 5 2
2 1 2
3 1 3
1 2 2
2 5 2