题目描述

Sasho 在休息时喜欢在纸上随手画一些图形。今天他刚读完一篇关于平面图、尤其是关于平面嵌入图的文章，于是纸上自然出现了一个无向、平面、连通且双连通的图。

回顾定义：

• 一个图称为平面图（这里按原题语境更准确地说是平面嵌入图），如果它的顶点是平面上的点，而边是平面上的曲线，并且这些边互不相交；
• 每个平面图都会把平面划分成若干个由图的边围成的区域；
• 这里的“区域”指的是简单区域，即其内部不包含图的边和顶点；
• 恰有一个外部的、无界的区域，其余都是内部区域；
• 这些区域称为面（faces）；
• 一个无向图称为双连通，如果删除任意一个顶点后，图仍保持连通。

Sasho 画好这个无向、平面、双连通图后，给每个内部面赋予了一个非负整数。然后他想到这样一个问题：

能不能给图的每条边也赋一个非负整数，使得围成每个内部面的那些边上的数之和，恰好等于这个面被赋予的数？

经过思考，Sasho 发现这并不总是可行。于是他把问题改成了：

能不能给每条边赋一个非负整数，使得对于所有内部面，围成该面的边权之和对某个统一的模数 M 取模后，等于该面被赋予的数字？

请编写程序 planegraph。给定一个无向、平面、双连通图，每个内部面的数字，以及一个正整数 M，求出一组边权，使其满足上述条件。

输入格式

第一行输入两个正整数 F 和 M，分别表示图中内部面的个数，以及取模所用的模数。

接下来 F 行，每行描述一个内部面。

每个面的描述格式如下：

K A1 A2 A3 ... AK S

其中：

• K：该面边界上的顶点个数；
• A1, A2, ..., AK：按顺序给出该面边界上的顶点编号；
• 围成该面的边依次为：
  • (A1, A2)
  • (A2, A3)
  • ...
  • (AK, A1)
• 图中的顶点按 1, 2, ... 顺序编号；
• 图中的每条边至少会在输入中出现一次；
• S：赋给该面的非负整数。

输出格式

如果问题有解，则对于图中的每条边，在单独一行输出三个整数 A B U：

• A 和 B 为该边两个端点的编号；
• U 为你赋给该边的值。

输出各条边的顺序任意；若有多组解，输出任意一组即可。

如果无解，输出：

-1

数据范围

$$1 \le F \le 100000$$ $$1 \le M \le 10^9$$ $$0 \le S < M$$ $$E \le 2F + 1$$

并且边权 U 必须满足：

$$0 \le U < M$$

说明

原题额外提醒，在平面图中，若 E 为边数、V 为点数、F 为面数，则有：

$$E \le 3V - 6$$ $$V - E + F = 2$$

子任务与评分

子任务	限制	分值
1	F \le 6，M \le 7	11
2	F \le 300，M 为质数	23
3	F \le 3000，M 为奇数	26
4	F \le 100000，M 任意	40

样例

输入

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

输出

1 2 2
2 3 0
1 3 0
2 4 0
1 4 2

样例解释

输入中给出的图有两个内部面：

• 一个由顶点 (1,2,3) 构成；
• 一个由顶点 (1,2,4) 构成。

第一个面上的边分别是：

• (1,2)，权值为 2
• (2,3)，权值为 0
• (3,1)，权值为 0

它们的和为：

$$2 + 0 + 0 = 2 \pmod 3$$

第二个面上的边分别是：

• (1,2)，权值为 2
• (2,4)，权值为 0
• (1,4)，权值为 2

它们的和为：

$$2 + 0 + 2 = 1 \pmod 3$$