Даны $n$ отрезков $[l_i, r_i]$ ($1 \le l_i \le r_i \le m$). Каждый отрезок имеет вес $c_i$.

Давайте выберем подпоследовательность отрезков, из каждого выбранного отрезка выберем целое число и расположим их в том же порядке, что и исходные отрезки. В результате этой операции мы получим целочисленную последовательность. Мы называем подпоследовательность отрезков «хорошей», если из неё можно составить неубывающую целочисленную подпоследовательность.

Пусть $k$ — максимальный вес хорошей подпоследовательности (сумма весов всех отрезков в подпоследовательности). Вычислите $k$ и количество хороших подпоследовательностей веса $k$. Поскольку количество подпоследовательностей может быть большим, вычислите его по модулю $998\,244\,353$.

Входные данные

Первая строка содержит единственное целое число $t$ ($1 \le t \le 10^4$) — количество тестовых случаев. Далее следует описание тестовых случаев.

Первая строка каждого тестового случая содержит два целых числа $n, m$ ($1 \le n, m \le 2 \cdot 10^5$).

Каждая из следующих $n$ строк содержит три целых числа $l_i, r_i, c_i$ ($1 \le l_i \le r_i \le m, 1 \le c_i \le 10^9$) — описание $i$-го отрезка.

Гарантируется, что сумма $n$ и сумма $m$ по всем тестовым случаям не превышают $2 \cdot 10^5$.

Выходные данные

Для каждого тестового случая выведите два целых числа — максимальный вес хорошей подпоследовательности и количество хороших подпоследовательностей с максимальным весом (второе число по модулю $998\,244\,353$).

Примеры

Входные данные 1

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

Выходные данные 1

3 1
6 1