Background

If time could go back to the past, perhaps, everything would be nothing but an illusion...

Little W travels through time and arrives in a four-dimensional space-time, where he begins his treasure hunt.

Problem Description

The entire four-dimensional space-time can be seen as a grid graph in four dimensions. Little W starts at position $(1,1,1,1)$, and the exit is at $(m,m,m,m)$. However, since Little W is from another time-space, his movements are restricted here. Each time, he can only increase one of the four coordinates by $1$. That is, he can only move one step to the right, up, forward, and * (the poor problem setter can't think of a way to describe this).

There are $n$ treasures in this space-time, with the $i$-th treasure located at $(a_i, b_i, c_i, d_i)$ and having a value of $v_i$.

Little W wants to know the maximum value sum of the treasures he can take. Since Little W also likes to plan ahead, he wants to find multiple different schemes that can achieve the maximum value sum. However, this number could be very large, so output it modulo $998244353$.

Note! Two schemes are considered different if and only if there is at least one treasure chosen differently in the two schemes. If the routes are different but the same treasures are chosen, they are not considered different schemes.

(Be careful if two treasures are at the same position...)

Input Format

The first line contains two numbers $n$ and $m$, representing the number of treasures and the maximum value of the grid coordinates, respectively.

The next $n$ lines each contain five numbers: $a_i, b_i, c_i, d_i, v_i$.

Output Format

Output two lines. The first line is the maximum value sum, and the second line is the number of schemes that meet the conditions, modulo $998244353$.

Sample Input and Output

Sample Input #1

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

Sample Output #1

16
1

Sample Input #2

20 1000000000
20204201 39958379 15138434 34289618 398078390
85600475 39563639 66410111 36702766 611878653
36702694 1628762 125746709 79172847 611878653
103077330 79188107 6711555 56295346 611878653
212677316 202221253 26717633 234187985 158044893
297040787 198938585 43827694 296390944 158044893
109256220 180224853 267561686 65767679 472347047
167183048 72650618 4390517 30073538 471045792
214834767 93996707 94416376 34549122 359059039
89445418 135311221 266840392 213735818 398078390
343357648 61588748 188180842 396968607 144378900
285457193 157755350 336368020 572049737 472347047
171728638 398663231 323772972 359470762 611878653
234684711 226541116 270561472 376433946 229386389
293174669 58119648 352134416 262971247 144378900
182250938 623413311 303663331 506122949 611878653
817319765 321076346 200801449 745136845 698518241
26356940 295529493 725103952 845588002 533478406
510252473 498314898 168621119 519205227 472347047
947274653 288133984 692904616 340022215 611878653

Sample Output #2

1696104353
6

Notes

For Sample 1, the best way is to slowly move from $(1,1,1,1)$ to $(3,1,3,1)$, and then slowly to $(5,5,5,5)$, obtaining a value of $16$. There is only one optimal path.

For all data, $1 \leq a_i, b_i, c_i, d_i \leq m$, and $1 \leq v_i \leq 10^9$.

见题面 Input 部分

见题面 Output 部分