題目敘述 : https://drive.google.com/file/d/1nDZNGCptQGcAZDxqRGcNt_wpz31clODZ/view?usp=sharing

房屋仲介小潮負責高談市的租房業務。小潮手上有編號為 $1, 2, · · · , n$ 的 $n$ 間待租的房屋，房屋 $i$ 的位置可以用二維座標 $(a_i, b_i)$ 表示，並且此房屋的月租金為 $r_i$ 元。

高談市有 $m$ 座捷運站，捷運站的編號為 $1, 2, · · · , m$，捷運站 $j$ 的位置在二維平面以座標 $(c_j , d_j )$ 表示。定義房屋 $i$ 與捷運站 $j$ 的距離為 $\sqrt{(a_i - c_j)^2 + (b_i - d_j)^2}$ 單位。

小潮發現租客的喜好如下：

1.    房屋與最近的捷運站的距離越短越好。
2.    如果兩間房屋和彼此最近的捷運站距離一樣近，月租金越小的房屋越好。
3.    如果兩間房屋和彼此最近的捷運站距離一樣近，而且月租金相同，房屋編號越小的越好。

請幫忙小潮開發一個房屋推薦系統，對房屋們進行排序，使得越是得到租客喜愛的房屋排在越前面。

如下圖為一 $n = 3$ 且 $m = 3$ 的例子，其中正方形的點 $H_1, H_2, H_3$ 分別代表房屋 $1, 2, 3$，圓點 $S_1, S_2, S_3$ 則分別代表捷運站 $1, 2, 3$ 的位置。並且：

•    第 $1$ 間房屋位在 $(2, 0)$，月租金為 $11000$ 元。
•    第 $2$ 間房屋位在 $(5, 0)$，月租金為 $12000$ 元。
•    第 $3$ 間房屋位在 $(3, 3)$，月租金為 $10000$ 元。
•    第 $1$ 座捷運站位在 $(1, 3)$。
•    第 $2$ 座捷運站位在 $(3, 0)$。
•    第 $3$ 座捷運站位在 $(5, 3)$。

測資限制

•    $1 ≤ n ≤ 10^5$。
•    $1 ≤ m ≤ 10^3$。
•    $−10^9 ≤ a_i, b_i, c_i, d_i ≤ 10^9$。
•    $0 ≤ r_i ≤ 10^9$
•    上述變數皆為整數。
•    任意一個座標最多只有一間房屋或一座捷運站，且不會有房屋和捷運站在同一座標。