题目描述

相邻两帧之间，同一个物体的检测框通常会有较大重叠。为了维持目标编号，具身智能部需要把上一帧轨迹框与当前帧候选框做一次简单的贪心关联。

给定上一帧的 N 条轨迹和当前帧的 M 个候选。请按 track_id 升序处理轨迹，为每条轨迹选择一个尚未使用、且 IoU 达到阈值的候选框。若没有可用候选，则输出 -1。

输入格式

• 第一行输入两个整数 N M。
• 随后 N 行，每行输入 track_id x1 y1 x2 y2。
• 再随后 M 行，每行输入 candidate_id x1 y1 x2 y2。
• 最后一行输入浮点数 Tmatch。

输出格式

• 按 track_id 升序输出 N 行。
• 每行输出 track_id matched_candidate_id；未匹配时 matched_candidate_id 为 -1。

判定规则

使用标准输出比较。

• 候选框一旦被某条轨迹匹配，之后不可再被使用。
• 对当前轨迹，只考虑 IoU >= Tmatch 的未使用候选。
• 若多个候选可选，优先选择 IoU 最大者；IoU 并列时选择 candidate_id 较小者。

样例

输入样例 1

2 2
2 0 0 10 10
1 20 20 30 30
7 21 21 31 31
5 1 1 9 9
0.5

输出样例 1

1 7
2 5

样例解释 1

轨迹按编号先处理 1 再处理 2，分别匹配到与自身重叠最高且达到阈值的候选。

输入样例 2

2 1
1 0 0 10 10
2 0 0 10 10
8 0 0 10 10
0.5

输出样例 2

1 8
2 -1

样例解释 2

候选 8 被轨迹 1 使用后不能复用，轨迹 2 无可匹配候选。