Bajtazar's kingdom consists of $n$ planets. A three-dimensional rectangular coordinate system has been introduced in the kingdom. For simplicity, each planet can be represented as a point in this coordinate system. The coordinate system was designed so that the coordinates of each planet are non-negative integers. No two planets are located at the same point.

Bajtazar would like to hand over the management of approximately $k$ of the planets to his daughter, Bajtynia. Bajtazar will separate the chosen planets using a fence in the shape of a rectangular cuboid, whose faces must be perpendicular to the coordinate axes. Bajtazar will be satisfied if he manages to separate between $k$ and $\lceil \frac{3}{2}k \rceil$ planets with the fence. (If $x$ is a real number, then $\lceil x \rceil$ denotes the smallest integer not less than $x$.) Planets located on the boundary of the fence count towards the result. The rectangular cuboid representing the fence may have sides of length 0. Help Bajtazar determine an appropriate position for the fence or state that it is impossible to plan the fence in this way.

Input

The first line of the input contains a single positive integer $t$ denoting the number of test cases to consider.

The first line of the description of the $i$-th test case contains two positive integers $n_i$ and $k_i$ ($2 \le k_i < n_i$), denoting the number of planets in the kingdom and the constraint on the number of planets that Bajtazar would like to separate with the fence, respectively. The $j$-th of the next $n_i$ lines of the description contains three integers $x_{i,j}$, $y_{i,j}$, and $z_{i,j}$ ($0 \le x_{i,j}, y_{i,j}, z_{i,j} \le 10^9$) denoting the coordinates of the $j$-th planet of Bajtazar.

Output

Your program should output exactly $t$ lines containing the answers for the individual test cases. If in the $i$-th test case it is possible to construct a fence in the shape of a rectangular cuboid with faces perpendicular to the coordinate axes, which contains between $k_i$ and $\lceil \frac{3}{2}k_i \rceil$ planets (counting the boundary of the cuboid), then the $i$-th line of the output should contain six integers $x'_i, y'_i, z'_i, x''_i, y''_i, z''_i$ ($0 \le x'_i, y'_i, z'_i, x''_i, y''_i, z''_i \le 10^9$, $x'_i \le x''_i$, $y'_i \le y''_i$, $z'_i \le z''_i$) indicating that the sought fence is $[x'_i, x''_i] \times [y'_i, y''_i] \times [z'_i, z''_i]$.

If in the $i$-th test case it is not possible to construct a fence according to Bajtazar's requirements, the $i$-th line of the output should contain a single number $-1$. If there are multiple possible answers, you may output any one of them.

Subtasks

The test set is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups. Let $N$ denote the sum of $n_1 + n_2 + \dots + n_t$ in a given test.

In each subtask, there is one group of tests worth 50% of the points, in which all planets have a $z$-coordinate equal to 0.

If in any test, in any test case, your program outputs a fence that contains more than $\lceil \frac{3}{2}k_i \rceil$ planets, but in all test cases of that test it outputs fences containing between $k_i$ and $3k_i$ planets, it will receive 25% of the points for that test.

Examples

Input 1

4
4 3
1 2 1
0 0 2
3 3 3
2 1 0
5 3
3 0 0
3 2 0
3 3 0
3 5 0
3 6 0
7 6
6 0 0
6 1 0
6 2 0
6 3 0
7 0 0
7 1 0
7 3 0
10 7
0 0 0
0 0 2
0 2 0
0 2 2
1 1 1
2 0 0
2 0 2
2 2 0
2 2 2
3 1 1

Output 1

0 0 0 2 2 2
3 2 0 3 6 0
6 0 0 7 3 0
0 0 0 2 2 2

Note

• In the first case, the fence contains exactly $k_1 = 3$ planets.
• In the second case, the fence contains 4 planets, although one could propose a fence that would contain $k_2 = 3$ planets. The problem conditions only require not exceeding $\lceil \frac{9}{2} \rceil = 5$ planets in the fence. The fence is in the shape of a line segment.
• In the third case, the fence contains all 7 planets. The problem conditions require not exceeding $\lceil \frac{3}{2}k_3 \rceil = 9$ planets in the fence. The fence is in the shape of a rectangle.
• In the fourth case, the fence contains 9 planets. The problem conditions require not exceeding $\lceil \frac{3}{2}k_4 \rceil = 11$ planets in the fence.