Barica 是一只非同寻常的青蛙。她住在一个池塘里，有 N 片漂浮在水面上的荷叶。这些荷叶的编号为 1 到 N，位置可以用一对坐标表示。Barica 可以在这些荷叶上跳来跳去，但是她害怕斜着跳和朝负方向跳。
准确的说，她可以从坐标 (x_1,y_1) 跳到另一个坐标 (x_2,y_2) 仅当：
x_2>x_1 且 y_2=y_1 或者
y_2>y_1 且 x_2=x_1。
对于每一片荷叶，我们知道其附近的苍蝇数量。Barika 可以吃掉所有在她荷叶附近的苍蝇。
Barica 每吃一只苍蝇会获得 1 个单位的能量，每进行一次跳跃消耗 K 个单位的能量。如果 Barica 没有足够的能量，她就不能进行跳跃。
Barica 想通过 1 号植物到达 N 号植物，并获得尽可能多的能量。Barica 开始时没有能量，必须通过吃掉 1 号植物附近的苍蝇来获取能量。
找到使得 Barica 达到目标的一种可行路径。
第一行，两个整数 N 和 K。
接下来 N 行，每行包含三个整数 x_i，y_i 和 z_i，表示第 i 号荷叶的坐标为 (x_i,y_i)，且其附近有 z_i 只苍蝇。
第一行，输出到达终点后能量单位数量。
第二行，输出一个整数 L，表示 Barica 需要经过的植物个数。必须包含 1 号和 N 号植物。
接下来 L 行，依次输出 Barica 需要经过的植物坐标。
6 5 1 1 5 2 1 5 1 2 4 2 3 5 3 2 30 3 3 5
5 4 1 1 2 1 2 3 3 3
8 10 1 1 15 2 2 30 1 2 8 2 1 7 3 2 8 2 3 7 4 2 100 3 3 15
36 5 1 1 1 2 2 2 3 2 3 3
9 5 5 5 10 6 5 2 7 5 1 5 6 2 6 6 6 7 6 2 5 7 1 6 7 2 7 7 1
2 3 5 5 7 5 7 7
对于 100\% 的数据，2\le N\le 3\times 10^5，1\le K\le 1000，0\le x_i,y_i\le 10^5，0\le z_i\le 1000。
COCI