Bạn được cho $n$ đoạn thẳng $[l_i, r_i]$ ($1 \le l_i \le r_i \le m$). Mỗi đoạn thẳng có một trọng số $c_i$.

Hãy chọn một dãy con các đoạn thẳng, từ mỗi đoạn thẳng đã chọn, chọn ra một số nguyên và sắp xếp chúng theo cùng thứ tự như các đoạn thẳng ban đầu. Bằng thao tác này, chúng ta sẽ thu được một dãy số nguyên. Chúng ta gọi một dãy con các đoạn thẳng là tốt nếu chúng ta có thể xây dựng một dãy con số nguyên không giảm từ đó.

Gọi $k$ là trọng số lớn nhất của một dãy con tốt (tổng trọng số của tất cả các đoạn thẳng trong dãy con đó). Hãy tính $k$ và số lượng các dãy con tốt có trọng số $k$. Vì số lượng dãy con có thể rất lớn, hãy tính kết quả theo modulo $998\,244\,353$.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $t$ ($1 \le t \le 10^4$) — số lượng bộ dữ liệu. Tiếp theo là mô tả các bộ dữ liệu.

Dòng đầu tiên của mỗi bộ dữ liệu chứa hai số nguyên $n, m$ ($1 \le n, m \le 2 \cdot 10^5$).

Mỗi dòng trong $n$ dòng tiếp theo chứa ba số nguyên $l_i, r_i, c_i$ ($1 \le l_i \le r_i \le m, 1 \le c_i \le 10^9$) — mô tả của đoạn thẳng thứ $i$.

Đảm bảo rằng tổng của $n$ và tổng của $m$ cho tất cả các bộ dữ liệu không vượt quá $2 \cdot 10^5$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra hai số nguyên — trọng số lớn nhất của một dãy con tốt và số lượng các dãy con tốt có trọng số lớn nhất đó (số thứ hai tính theo modulo $998\,244\,353$).

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

3 1
6 1