The country of JOI has decided to start television broadcasting. There are $N$ houses in the country of JOI. To ensure that television broadcasts can be viewed in all of these houses, it is necessary to build radio towers.

The King of JOI has decided to build $K$ radio towers. If the $i$-th radio tower is built at coordinates $(X_i, Y_i)$ and its output level is set to $E_i$, television broadcasts can be viewed in houses at a distance of $\sqrt{E_i}$ or less from $(X_i, Y_i)$ (the distance between two points $(a, b)$ and $(c, d)$ is given by $\sqrt{(a - c)^2 + (b - d)^2}$). However, setting the output level of a radio tower to $E_i$ consumes $E_i$ units of energy. We want to minimize the total energy consumed by the $K$ radio towers (hereinafter simply referred to as "energy consumption") while ensuring that television broadcasts can be viewed in all houses. Radio towers can be built at coordinates where houses are located, and two towers can be built at the same coordinates.

Given the coordinates of the houses in the country of JOI, you want to determine the locations and output levels of the radio towers so that all houses can receive television broadcasts.

Input

The input file is given in the following format:

• The first line contains two space-separated integers $N$ and $K$, representing the number of houses in the country of JOI and the number of radio towers to be built, respectively.
• The following $N$ lines, the $i$-th line ($1 \le i \le N$), contains two space-separated integers $A_i$ and $B_i$, representing the coordinates $(A_i, B_i)$ of the $i$-th house.

You may assume that no two houses are at the same coordinates.

Output

Output $K$ lines, where the $i$-th line ($1 \le i \le K$) contains three space-separated integers $X_i, Y_i, E_i$ ($0 \le X_i \le 1\,000\,000$, $0 \le Y_i \le 1\,000\,000$, $0 \le E_i \le 1\,000\,000\,000\,000$ ($= 10^{12}$)).

Constraints

• $1 \le N \le 500$
• $1 \le K \le 30$
• $0 \le A_i, B_i \le 1\,000\,000$

Subtasks

For each input data, your score is calculated as follows:

Let $E_0$ be the minimum energy consumption among all outputs submitted by participants. If your submitted output does not satisfy the problem conditions, your score is 0. If it satisfies the conditions, let $E$ be the energy consumption of your submitted output:

• If $\frac{E}{E_0} > 1.5$, your score is 0.
• If $\frac{E}{E_0} \le 1.5$, your score is the value obtained by rounding to the nearest integer: $$\left( 4 \times \left( 1.5 - \frac{E}{E_0} \right)^2 \right) \times 20$$

Examples

Input 1

10 3
0 300000
500000 800000
700000 200000
100000 500000
400000 900000
200000 1000000
300000 500000
300000 200000
500000 100000
1000000 0

Output 1

200000 700000 160000000000
300000 300000 90000000000
750000 0 62500000000

Note

This input/output example corresponds to the figure below. Each circle represents the range within a distance of $\sqrt{E_i}$ from the coordinates $(X_i, Y_i)$. In this case, the energy consumption is $160\,000\,000\,000 + 90\,000\,000\,000 + 62\,500\,000\,000 = 312\,500\,000\,000$ (312.5 billion).