B - ★★体育课排队★★

时间限制： 1000ms

空间限制： 256MB

题目描述

今天体育老师终于没有生病了，同学们欢快地提前来到操场准备上体育课。
将操场视为一个二维平面，现在每个同学都在整数坐标表示的位置上玩耍，起初有可能有多位同学处于同一位置。为了避免老师再次被气倒，同学们需要在上课之前分为 m 队，并且每队要按 $x$ 轴正方向整齐地排列，其中第 $i$ 队队首的位置为 $(sx_{i},sy_{i})$，排队全部完成之后每支队伍里同学们的位置必须是连续的且不能有多位同学处于同一位置(排队过程中没有该限制)。
例如第 $i$ 队要有 $s_{i}$ 位同学，则应按任意的顺序分别排在 $(sx_{i},sy_{i}),(sx_{i}+1,sy_{i}),\cdots ,(sx_{i}+s_{i}-1,sy_{i})$ 这 $s_{i}$​ 个位置上。
在排队开始之前，所有同学会一直停在初始位置。当排队开始时，所有的同学会在这一时刻同时开始移动，在每秒钟，每位同学可以向上下左右四个方向中的任意方向移动一个单位长度，或者留在原地。例如当前位置为 $(x,y)$，则下一秒可以移动到$(x,y),(x+1,y),(x-1,y),(x,y+1),(x,y-1)$其中的一个位置。
$Bob$ 身为班级的一员，他想让同学们尽可能多地玩耍，但是也要保证同学们能在体育课开始的瞬间排好队。因此他想知道，在采取最优策略的情况下，至少需要提前多少秒开始排队。当然，同学们可以自由选择自己要去的队伍。
(忽略同学们之间的碰撞体积)

输入描述:

第一行一个整数 $T  (1 \leq T \leq 1000)$，表示测试用例的数量。
对于每组测试用例，第一行两个整数 $n,m(1 \leq m \leq n\leq 1000)$，分别表示学生的数量和要分的队数；
接下来 $n$ 行，第 $i (1 \leq i \leq n)$ 行两个整数 $x_{i},y_{i}$; $(-1000 \leq x_{i},y_{i} \leq 1000)$​，表示第 $i$ 位学生的位置；
接下来 $m$ 行，第 $i   (1 \leq i \leq m)$ 行三个整数 $s_{i},sx_{i},sy_{i}$ $(1 \leq s_{i} \leq n,-1000 \leq sx_{i},sy_{i} \leq 1000)$，分别表示第 $i$ 队要排的人数和队首位置。
对于每组测试用例，保证队首的纵坐标各不相同，且 $\sum s=n$。
对于全部测试用例，保证 $\sum n \leq 1000$。

输出描述:

对于每组测试用例，先在第一行输出一个整数表示排好队所需的最短时间；
接下来 $m$行，第$i (1 \leq i \leq m)$ 行 $s_{i}$​ 个整数，表示第 $i$ 队从队首到队尾每个位置学生的编号。
如果有多种答案，你可以输出其中任意一种。

输入

2
5 1
0 5
5 1
-2 0
3 1
2 2
5 -1 0
10 2
-990 -132
513 41
32 241
274 582
-980 -891
-982 -529
-414 290
721 -565
925 -966
-368 -773
5 554 0
5 -563 4

输出

5
3 1 2 4 5
1333
7 2 4 8 9
3 5 6 1 10

说明

在第一组测试用例中，五位同学可按 $3,1,2,4,5$ 的顺序排成一队，所需时间最短为 $5$。
在第二组测试用例中，所需最短时间为 $1333$。