Vous disposez de $n$ segments $[l_i, r_i]$ ($1 \le l_i \le r_i \le m$). Chaque segment possède un poids $c_i$.

Choisissons une sous-suite de segments, choisissons un entier dans chaque segment choisi et arrangeons-les dans le même ordre que les segments initiaux. Par cette opération, nous obtenons une suite d'entiers. Nous disons qu'une sous-suite de segments est bonne si nous pouvons construire une sous-suite d'entiers non décroissante à partir de celle-ci.

Soit $k$ le poids maximum d'une bonne sous-suite (la somme des poids de tous les segments de la sous-suite). Calculez $k$ et le nombre de bonnes sous-suites de poids $k$. Comme le nombre de sous-suites peut être grand, calculez-le modulo $998\,244\,353$.

Entrée

La première ligne contient un entier unique $t$ ($1 \le t \le 10^4$) — le nombre de cas de test. La description des cas de test suit.

La première ligne de chaque cas de test contient deux entiers $n, m$ ($1 \le n, m \le 2 \cdot 10^5$).

Chacune des $n$ lignes suivantes contient trois entiers $l_i, r_i, c_i$ ($1 \le l_i \le r_i \le m$, $1 \le c_i \le 10^9$) — la description du $i$-ème segment.

Il est garanti que la somme de $n$ et la somme de $m$ pour tous les cas de test n'excèdent pas $2 \cdot 10^5$.

Sortie

Pour chaque cas de test, affichez deux entiers — le poids maximum d'une bonne sous-suite et le nombre de bonnes sous-suites ayant ce poids maximum (le second nombre modulo $998\,244\,353$).

Exemples

Entrée 1

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

Sortie 1

3 1
6 1