$n$개의 구간 $[l_i, r_i]$ ($1 \le l_i \le r_i \le m$)가 주어지며, 각 구간은 가중치 $c_i$를 가집니다.

구간의 부분 수열을 선택하고, 선택된 각 구간에서 정수를 하나씩 골라 원래 구간의 순서대로 나열하여 정수 수열을 만든다고 합시다. 이때, 비내림차순 정수 수열을 만들 수 있는 구간의 부분 수열을 좋은(good) 부분 수열이라고 합니다.

좋은 부분 수열의 최대 가중치(부분 수열에 포함된 모든 구간의 가중치 합)를 $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$개의 줄에는 $i$번째 구간에 대한 설명으로 세 정수 $l_i, r_i, c_i$ ($1 \le l_i \le r_i \le m, 1 \le c_i \le 10^9$)가 주어집니다.

모든 테스트 케이스에 대해 $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