一般に、Tangle に基づく暗号通貨は次のように動作します。Tangle と呼ぶ有向非巡回グラフ（DAG）があります。DAG のネットワークはノードからなり、ノードは取引を発行し検証する主体です。ノードが発行した取引は、取引を保存する台帳である Tangle グラフの頂点集合を構成します。Tangle の辺集合は次のように得られます。新しい取引 $X$ が来ると、以前の 2 つの取引を承認しなければなりません。この承認は図 4(a) のように有向辺で表されます。取引 $A$ と $G$ の間に有向辺がなくても、$A$ から $G$ へ長さが 2 以上の有向経路があるとき、$A$ は $G$ を間接的に承認するといいます。図 4(a) では $A$ は $B$ と $D$ を直接承認し、$F$、$G$、$H$、$I$ を間接的に承認します。Tangle グラフで未承認の取引を「Tip」と定義します。図 4(a) の Tangle の状態では Tip は $A$ と $C$ です。新しい取引 $X$ が到着し、図 4(b) の状態のように $A$ と $C$ を承認すると、$X$ が唯一の Tip になります。

図 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$ に達すると、悪意ある改変の確率が低いため、取引は確認済みとして扱われます。つまり、取引が追加の承認を受けるほど、システムはより高い信頼度でそれを受け入れます。承認されていて累積重みが上限未満の取引を未確認取引と呼びます。$TH=12$ とすると、図 4 の $F$、$G$、$H$、$I$ は確認済みです。Tangle の初めには、すべてのトークンを残高に持つアドレスがありました。Genesis 取引はこれらを複数の「創設者」アドレスに送りました。すべてのトークンは Genesis 取引で作られました。したがって、Genesis 取引は他のすべての取引によって直接または間接的に承認されます（図 5）。ノードが取引を作る際、最初に Tip 選択アルゴリズムに基づき 2 つの Tip（未承認取引）を選びます。新しい取引は以前の 2 つの取引を承認し、これは有向辺で表されます。ネットワークの他のノードは取引を検証し、DAG に新しい Tip として追加します。Tip として追加された取引は未承認です。その後の取引がその Tip を選ぶと承認済みになります。取引がそれを直接または間接的に承認するたびに、その取引の累積重みは更新されます。

図 5：各取引に重みを付けた Tangle グラフ

説明のため、初期の Tangle を図 6(a) に示します。新しく作られた取引 $X$ は、Tip 選択アルゴリズムに基づき 2 つの Tip $Y$、$Z$（未承認取引）を選びます。図 6(b) は $X$、$Y$、$Z$ それぞれの重みと累積重みの表記を示します。

(a) 初期の Tangle。(b) $X$ が $Y$ と $Z$ を承認。 図 6：各取引に重みを付けた Tangle グラフ

図 7：入力例 1 の Tangle グラフ。$TH=12$ であり、$T_2$ と $T_3$ について $CW_X \ge TH$ です。

入力

入力の最初の行は整数の組 $n$、$TH$ です。$n$ は取引数、$TH$ は累積重みの閾値を表します。取引は $X$ の昇順で入力されます。各取引は 1 行の整数列 $X$, $Y$, $Z$, $W_X$ であり、$2 \le X \le 10000$、$0 \le Y,Z \le X-1$、$Y \ne 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 \ne Z$

出力

$n$ 個の取引を処理した後、$\{T_2,T_3,\ldots,T_n\}$ に属する取引 $T_X$ について $CW_X \ge TH$ なら、値 $X$ と $CW_X$ の組を $X$ の昇順で出力してください。各行には 1 つの取引を出力します。最後に、確認済み取引の総数を出力してください。

入出力例

入力 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