全世界有 $N$ 家酒店。每家酒店都有一个位置和一个价格。$M$ 位顾客想要找到一家价格可接受且距离他们位置最近的酒店。距离采用欧几里得距离衡量。

输入格式

第一行包含一个整数，表示测试用例的数量。

对于每个测试用例： 第一行包含两个整数 $N$ ($N \le 200000$) 和 $M$ ($M \le 20000$)。

接下来的 $N$ 行，每行描述一家酒店，包含 $3$ 个整数 $x$ ($1 \le x \le N$)、$y$ ($1 \le y \le N$) 和 $c$ ($1 \le c \le N$)，其中 $x$ 和 $y$ 是酒店的坐标，$c$ 是其价格。保证这 $N$ 家酒店的 $x$ 坐标互不相同，$y$ 坐标互不相同，且价格 $c$ 也互不相同。

接下来的 $M$ 行，每行描述一位顾客的查询，包含 $3$ 个整数 $x$ ($1 \le x \le N$)、$y$ ($1 \le y \le N$) 和 $c$ ($1 \le c \le N$)，其中 $x$ 和 $y$ 是顾客的坐标，$c$ 是该顾客能接受的最大价格。

输出格式

对于每位顾客的查询，输出价格可接受且距离顾客位置最近的酒店的信息（即其坐标和价格）。如果有多个价格可接受且距离最近的酒店，输出在输入中最早出现的那一个。

样例

样例输入 1

2
3 3
1 1 1
3 2 3
2 3 2
2 2 1
2 2 2
2 2 3
5 5
1 4 4
2 1 2
4 5 3
5 2 1
3 3 5
3 3 1
3 3 2
3 3 3
3 3 4
3 3 5

样例输出 1

1 1 1
2 3 2
3 2 3
5 2 1
2 1 2
2 1 2
1 4 4
3 3 5