$n$ 個の区間 $[l_i, r_i]$ ($1 \le l_i \le r_i \le m$) が与えられます。各区間には重み $c_i$ が割り当てられています。

区間の部分列を選び、選んだ各区間から整数を1つずつ選び、元の区間の順序と同じ順序で並べることで、整数の列を作ります。このとき、作られた整数の列が広義単調増加列となるような区間の部分列を「良い」部分列と呼びます。

「良い」部分列の重みの最大値を $k$ とします（ここで重みとは、部分列に含まれるすべての区間の重みの和を指します）。$k$ と、重みが $k$ である「良い」部分列の個数を求めてください。部分列の個数は非常に大きくなる可能性があるため、$998\,244\,353$ で割った余りを求めてください。

Input

1行目にはテストケースの数 $t$ ($1 \le t \le 10^4$) が与えられます。続いて各テストケースが与えられます。

各テストケースの1行目には、2つの整数 $n, m$ ($1 \le n, m \le 2 \cdot 10^5$) が与えられます。

続く $n$ 行には、各区間の情報として3つの整数 $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$ を超えないことが保証されています。

Output

各テストケースについて、「良い」部分列の重みの最大値と、その重みを持つ「良い」部分列の個数（$998\,244\,353$ を法とする）を空白区切りで出力してください。

Example

入力 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