Se te dan $n$ segmentos $[l_i, r_i]$ ($1 \le l_i \le r_i \le m$). Cada segmento tiene un peso $c_i$.

Elijamos una subsecuencia de segmentos, de cada segmento elegido escojamos un entero y ordenémoslos en el mismo orden que los segmentos iniciales. Mediante esta operación obtendremos una secuencia de enteros. Decimos que una subsecuencia de segmentos es buena si podemos construir una subsecuencia de enteros no decreciente a partir de ella.

Sea $k$ el peso máximo de una subsecuencia buena (la suma de los pesos de todos los segmentos en la subsecuencia). Calcula $k$ y el número de subsecuencias buenas de peso $k$. Dado que el número de subsecuencias puede ser grande, calcúlalo módulo $998\,244\,353$.

Entrada

La primera línea contiene un único entero $t$ ($1 \le t \le 10^4$) — el número de casos de prueba. A continuación sigue la descripción de los casos de prueba.

La primera línea de cada caso de prueba contiene dos enteros $n, m$ ($1 \le n, m \le 2 \cdot 10^5$).

Cada una de las siguientes $n$ líneas contiene tres enteros $l_i, r_i, c_i$ ($1 \le l_i \le r_i \le m$, $1 \le c_i \le 10^9$) — la descripción del $i$-ésimo segmento.

Se garantiza que tanto la suma de $n$ como la suma de $m$ para todos los casos de prueba no exceden $2 \cdot 10^5$.

Salida

Para cada caso de prueba, imprime dos enteros — el peso máximo de una subsecuencia buena y el número de subsecuencias buenas con peso máximo (el segundo número módulo $998\,244\,353$).

Ejemplos

Entrada 1

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

Salida 1

3 1
6 1