Ogólnie kryptowaluta oparta na Tangle działa następująco. Istnieje skierowany graf acykliczny (DAG), który nazywamy Tangle. Sieć DAG składa się z węzłów, czyli podmiotów wystawiających i weryfikujących transakcje. Transakcje wystawione przez węzły tworzą zbiór wierzchołków grafu Tangle, będącego księgą przechowującą transakcje. Zbiór krawędzi powstaje tak: gdy pojawia się nowa transakcja $X$, musi zatwierdzić dwie wcześniejsze. Zatwierdzenia przedstawiają skierowane krawędzie, jak na rysunku 4(a). Jeśli nie ma skierowanej krawędzi między transakcjami $A$ i $G$, ale istnieje skierowana ścieżka długości co najmniej dwa z $A$ do $G$, mówimy, że $A$ pośrednio zatwierdza $G$. Na rysunku 4(a) $A$ bezpośrednio zatwierdza $B$ i $D$, a pośrednio $F$, $G$, $H$ i $I$. Zdefiniujmy „Tip” jako niezatwierdzoną transakcję w grafie Tangle. W stanie z rysunku 4(a) Tipami są $A$ i $C$. Gdy nowa transakcja $X$ zatwierdzi $A$ i $C$ w stanie z rysunku 4(b), $X$ staje się jedynym Tipem.

Rysunek 4: Graf Tangle z wagami przed i po wystawieniu nowej transakcji $X$. Prostokąty oznaczają transakcje, mała liczba w prawym dolnym (południowo-wschodnim, SE) rogu każdego to jego własna waga, a pogrubiona liczba to waga skumulowana.

Definiujemy wagę transakcji i związane pojęcia. Waga jest proporcjonalna do pracy włożonej w transakcję przez wystawiający ją węzeł. Ważne jest tylko, że do każdej transakcji przypisana jest dodatnia liczba całkowita, jej waga. Ogólnie transakcja o większej wadze jest „ważniejsza” od transakcji o mniejszej wadze. Załóżmy, że własna waga transakcji $X$ wynosi $W_X$, gdzie $1 \le W_X \le W_{\max}$. Skumulowana waga $CW_X$ transakcji $X$ to suma jej wagi oraz wag wszystkich transakcji bezpośrednio lub pośrednio ją zatwierdzających. Obliczenie zilustrowano na rysunku 4. Prostokąty oznaczają transakcje, mała liczba w prawym dolnym rogu to własna waga, a pogrubiona liczba to waga skumulowana. Na przykład transakcję $F$ bezpośrednio lub pośrednio zatwierdzają $A$, $B$, $C$ i $E$.

Skumulowana waga $F$ wynosi $CW_F=3+1+3+1+1=9$: to suma własnej wagi $F$ oraz wag odpowiednio $A$, $B$, $C$ i $E$. Po zatwierdzeniu przez nową transakcję $X$ ($W_X=3$) skumulowana waga wszystkich innych transakcji zwiększa się o $3$. Skumulowana waga jest miarą wysiłku obliczeniowego stojącego za transakcją. Gdy osiąga próg $TH$, transakcję oznacza się jako potwierdzoną, ponieważ prawdopodobieństwo złośliwej modyfikacji jest małe. Innymi słowy, gdy otrzymuje dodatkowe zatwierdzenia, system akceptuje ją z większą pewnością. Zatwierdzone transakcje o wadze skumulowanej mniejszej od górnego limitu nazywamy niepotwierdzonymi. Przy $TH=12$ transakcje $F$, $G$, $H$ i $I$ na rysunku 4 są potwierdzone. Na początku Tangle istniał adres z saldem zawierającym wszystkie tokeny. Transakcja Genesis wysłała je na kilka innych adresów „założycieli”. Wszystkie tokeny utworzono w transakcji Genesis. Dlatego wszystkie inne transakcje bezpośrednio lub pośrednio zatwierdzają Genesis (rysunek 5). Gdy węzeł tworzy transakcję, początkowo wybiera dwa Tipy (niezatwierdzone transakcje) algorytmem wyboru Tipów. Każda nowa transakcja powinna zatwierdzić dwie wcześniejsze, co przedstawiają skierowane krawędzie. Pozostałe węzły weryfikują transakcję i dodają ją jako nowy Tip do DAG. Po dodaniu jako Tip transakcja jest niezatwierdzona. Gdy dalsza transakcja wybierze ten Tip, staje się zatwierdzony. Skumulowana waga związana z transakcją jest aktualizowana zawsze, gdy inna transakcja zatwierdza ją bezpośrednio lub pośrednio.

Rysunek 5: Graf Tangle z wagami przypisanymi każdej transakcji

Dla wygody początkowy Tangle przedstawiono na rysunku 6(a). Nowo utworzona transakcja $X$ wybierze dwa Tipy $Y$ i $Z$ (niezatwierdzone transakcje) algorytmem wyboru Tipów. Rysunek 6(b) pokazuje oznaczenia wag i wag skumulowanych odpowiednio dla $X$, $Y$ i $Z$.

(a) Początkowy Tangle. (b) $X$ zatwierdza $Y$ i $Z$. Rysunek 6: Graf Tangle z wagami przypisanymi każdej transakcji

Rysunek 7: Graf Tangle dla przykładowego wejścia 1, gdzie $TH=12$ ($CW_X \ge TH$ dla $T_2$ i $T_3$).

Wejście

Pierwszy wiersz zawiera parę liczb całkowitych $n$, $TH$, gdzie $n$ to liczba transakcji, a $TH$ to próg wagi skumulowanej. Transakcje podano w rosnącej kolejności $X$. Każda zajmuje jeden wiersz z listą liczb całkowitych $X$, $Y$, $Z$, $W_X$, gdzie $2 \le X \le 10000$, $0 \le Y,Z \le X-1$, $Y \ne Z$ oraz $1 \le W_X \le 5$.

Ograniczenia

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

Wyjście

Po przetworzeniu $n$ transakcji, dla każdej transakcji $T_X$ ze zbioru $\{T_2,T_3,\ldots,T_n\}$, jeśli $CW_X \ge TH$, wypisz wartości $X$ i $CW_X$ w rosnącej kolejności $X$. Każdy wiersz zawiera jedną transakcję. Na końcu wypisz całkowitą liczbę potwierdzonych transakcji.

Przykład

Wejście 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

Wyjście 1

2 18
3 14
2