B. Standard Problem
time limit per test
2 seconds
memory limit per test
512 mebibytes
input
standard input
output
standard output

You are given $$$n$$$ segments $$$[l_i,r_i]$$$ ($$$1 \le l_i \le r_i \le m$$$). Each segment has a weight $$$c_i$$$.

Let us choose a subsequence of segments, from each chosen segment choose an integer and arrange them in the same order as initial segments. By this operation we will get an integer sequence. We say that a subsequence of segments is good if we can construct a nondecreasing integer subsequence from it.

Let $$$k$$$ be the maximum weight of a good subsequence (the sum of weights of all segments in the subsequence). Calculate $$$k$$$ and the number of good subsequences of weight $$$k$$$. Since the number of subsequences can be large, calculate it modulo $$$998\,244\,353$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. Description of test cases follows.

The first line of each test case contains two integers $$$n$$$, $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$).

Each of the next $$$n$$$ lines contains three integers $$$l_i$$$, $$$r_i$$$, $$$c_i$$$ ($$$1 \le l_i \le r_i \le m$$$, $$$1 \le c_i \le 10^9$$$) — description of the $$$i$$$-th segment.

It is guaranteed that both the sum of $$$n$$$ and the sum of $$$m$$$ for all test cases do not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print two integers — the maximum weight of a good subsequence and the number of good subsequences with maximum weight (the second number modulo $$$998\,244\,353$$$).

Example
Input
2
3 4
1 2 1
2 3 1
2 2 1
2 5
1 4 3
2 5 3
Output
3 1
6 1