C. Cakes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard 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 105 operations on the n stacks.

Let si 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 sA ≥ (a - 1)·sB.
  3. Cactus moves (a - 1)·sB 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 yi, zi, and ti, representing an operation where Cactus should choose the integer ti, and move cakes from stack yi to stack zi.

Your solution will be considered correct if 0 ≤ x ≤ 105, 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.

Example
Input
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