일반적으로 Tangle 기반 암호화폐는 다음과 같이 작동한다. Tangle이라고 부르는 방향 비순환 그래프(DAG)가 있다. DAG의 네트워크는 노드로 이루어져 있으며, 노드는 거래를 발행하고 검증하는 주체이다. 노드가 발행한 거래는 거래를 저장하는 원장인 Tangle 그래프의 정점 집합을 이룬다. Tangle의 간선 집합은 다음과 같이 만들어진다. 새 거래 $X$가 도착하면 이전 거래 두 개를 승인해야 한다. 이 승인은 그림 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 선택 알고리즘으로 두 Tip(미승인 거래)을 선택한다. 새 거래는 이전 두 거래를 승인해야 하며, 이는 방향 간선으로 표시된다. 네트워크의 다른 노드들은 거래를 검증하고 DAG에 새 Tip으로 추가한다. 거래가 DAG에 Tip으로 추가되면 아직 승인되지 않은 상태이다. 이후 어떤 거래가 그 Tip을 선택하면 승인된 상태가 된다. 어떤 거래가 해당 거래를 직접 또는 간접 승인할 때마다 관련 누적 가중치가 갱신된다.

그림 5: 각 거래의 가중치가 표시된 Tangle 그래프

편의를 위해 초기 Tangle을 그림 6(a)에 보인다. 새로 생성된 거래 $X$는 Tip 선택 알고리즘으로 두 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$가 증가하는 순서로 입력된다. 각 거래는 한 줄에 정수 목록 $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

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