给定 $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$ 行，每行包含三个整数 $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