Dany jest zbiór $n$ przedziałów $[l_i, r_i]$ ($1 \le l_i \le r_i \le m$). Każdy przedział ma wagę $c_i$.

Wybierzmy podciąg przedziałów, z każdego wybranego przedziału wybierzmy liczbę całkowitą i ustawmy je w tej samej kolejności, w jakiej występowały w początkowym ciągu przedziałów. W wyniku tej operacji otrzymamy ciąg liczb całkowitych. Mówimy, że podciąg przedziałów jest dobry, jeśli możemy z niego skonstruować niemalejący podciąg liczb całkowitych.

Niech $k$ będzie maksymalną wagą dobrego podciągu (suma wag wszystkich przedziałów w podciągu). Oblicz $k$ oraz liczbę dobrych podciągów o wadze $k$. Ponieważ liczba podciągów może być duża, oblicz ją modulo $998\,244\,353$.

Wejście

Pierwsza linia zawiera jedną liczbę całkowitą $t$ ($1 \le t \le 10^4$) — liczbę zestawów danych. Następnie następuje opis zestawów danych.

Pierwsza linia każdego zestawu danych zawiera dwie liczby całkowite $n, m$ ($1 \le n, m \le 2 \cdot 10^5$).

Każda z kolejnych $n$ linii zawiera trzy liczby całkowite $l_i, r_i, c_i$ ($1 \le l_i \le r_i \le m$, $1 \le c_i \le 10^9$) — opis $i$-tego przedziału.

Gwarantuje się, że suma $n$ oraz suma $m$ dla wszystkich zestawów danych nie przekraczają $2 \cdot 10^5$.

Wyjście

Dla każdego zestawu danych wypisz dwie liczby całkowite — maksymalną wagę dobrego podciągu oraz liczbę dobrych podciągów o maksymalnej wadze (drugą liczbę modulo $998\,244\,353$).

Przykład

Wejście 1

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

Wyjście 1

3 1
6 1