通常，基于 Tangle 的加密货币的工作方式如下。存在一个有向无环图（DAG），我们称之为 Tangle。Tangle 网络由节点组成，即发行和验证交易的实体。节点发出的交易构成了 Tangle 图的站点集，这是存储交易的账本。Tangle 的边集通过以下方式获得：当一个新的交易 $X$ 到达时，它必须批准两个先前的交易。这些批准由有向边表示，如图 4(a) 所示。如果交易 $A$ 和交易 $G$ 之间没有直接的有向边，但存在一条从 $A$ 到 $G$ 且长度至少为 2 的有向路径，我们称 $A$ 间接批准了 $G$。在图 4(a) 中，$A$ 直接批准了 $B$ 和 $D$，并间接批准了 $F$、$G$、$H$ 和 $I$。我们将 Tangle 图中未被批准的交易定义为“提示”（Tips）。在图 4(a) 的 Tangle 快照中，提示是 $A$ 和 $C$。当新交易 $X$ 到达并批准 $A$ 和 $C$ 时，在图 4(b) 的 Tangle 快照中，$X$ 成为唯一的提示。

图 4：带有新发行交易 $X$ 前后权重分配的 Tangle 图。方框代表交易，每个方框右下角（SE）的小数字表示自身权重，粗体数字表示累积权重。

我们定义交易的权重及相关概念。交易的权重与发行节点投入的工作量成正比。重要的是，每笔交易都有一个与之关联的正整数权重。通常，权重较大的交易比权重较小的交易更“重要”。假设交易 $X$ 的自身权重等于 $W_X$，其中 $1 \le W_X \le W_{max}$。$X$ 的累积权重 $CW_X$ 是其自身权重与所有直接或间接批准它的交易的权重之和。累积权重的计算如图 4 所示。方框代表交易，每个方框右下角的小数字表示自身权重，粗体数字表示累积权重。例如，交易 $F$ 被交易 $A$、$B$、$C$ 和 $E$ 直接或间接批准。

$F$ 的累积权重为 $CW_F = 3 + 1 + 3 + 1 + 1 = 9$，这是 $F$ 的自身权重与 $A$、$B$、$C$ 和 $E$ 的权重之和。在新交易 $X$ ($W_X = 3$) 批准后，所有其他交易的累积权重增加 3。交易的累积权重是其背后计算工作量的度量。因此，一旦达到阈值 $TH$，该交易就被标记为已确认，因为恶意修改的可能性很低。换句话说，随着交易获得额外的批准，它被系统以更高的置信度接受。累积权重小于上限的已批准交易称为未确认交易。如图 4 所示，如果我们假设 $TH = 12$，则交易 $F$、$G$、$H$ 和 $I$ 是已确认的。在 Tangle 的开始，有一个余额地址包含了所有的代币。Genesis 交易将这些代币发送给其他几个“创始人”地址。所有的代币都是在 Genesis 交易中创建的。因此，“Genesis”交易被所有其他交易直接或间接批准（如图 5 所示）。最初，当一个节点创建交易时，它会根据提示选择算法选择两个提示（未批准的交易）。每笔新交易都应批准两个先前的交易，这些批准由有向边表示。网络中的其他节点将验证该交易并将其作为新的提示添加到 DAG 中。当交易作为提示添加到 DAG 中时，它是未批准的。当任何后续交易选择该提示时，它就变成了已批准。每当有交易直接/间接批准某笔交易时，与该交易相关的累积权重就会更新。

图 5：每个交易带有权重分配的 Tangle 图

为方便起见，初始 Tangle 如图 6(a) 所示。新创建的交易 $X$ 将根据提示选择算法选择两个提示 $Y$ 和 $Z$（未批准的交易）。图 6(b) 显示了 $X$、$Y$ 和 $Z$ 的权重和累积权重的符号。

图 6：每个交易带有权重分配的 Tangle 图

图 7：样例输入 1 的 Tangle 图，其中 $TH = 12$（$T_2$ 和 $T_3$ 的 $CW_X \ge TH$）。

输入格式

输入的第一行是一对整数 $n$ 和 $TH$，其中 $n$ 表示交易数量，$TH$ 表示累积权重的阈值。交易按 $X$ 的递增顺序输入。每笔交易占一行，包含一系列整数：$X \ Y \ Z \ W_X$，其中 $2 \le X \le 10000$，$0 \le Y, Z \le X - 1$，$Y \neq Z$，且 $1 \le W_X \le 5$。

数据范围

• $1 \le n \le 10000$
• $2 \le X \le n + 1$
• $0 \le Y, Z \le X - 1, Y \neq Z$

输出格式

处理完 $n$ 笔交易后，对于 $\{T_2, T_3, \dots, T_n\}$ 中的交易 $T_X$，如果 $CW_X \ge TH$，则按 $X$ 的递增顺序输出值列表：$X \ CW_X$。每行包含一笔交易。最后，输出已确认交易的总数。

样例

输入 1

6 12
2 0 1 3
3 0 2 2
4 1 2 1
5 2 3 3
6 3 4 4
7 3 5 5

输出 1

2 18
3 14
2