P8502 "CGOI-2" No cost too great

The Radiance seeps into Hallownest; she is making a huge mistake. With only a little faith left, why does she still insist. I will be a lighthouse, shining upon the kingdom. But before that, there are more important things to do. No matter what the cost is, I will not hesitate, even though I have little left...

The Pale King is making his final visit to the magnificent palace he built. Now suppose the palace consists of $n$ rooms, with some **directed** corridors between rooms. Due to the Pale King's strange decorating habit (not referring to putting circular saws everywhere), for room $i$, it has a directed corridor to every room whose index lies in the interval $[l_i, r_i]$. For example, if room $4$ has directed corridors to $[2,5]$, it means there is a directed corridor from room $4$ to each of rooms $2, 3, 4, 5$ (a room may have a corridor to itself). If a room has corridors to $[0,0]$, it means there is no outgoing corridor from that room. The Pale King asks $q$ questions. Each query asks for the number of ways to go from room $a$ to room $b$ using exactly $m$ directed corridors and without passing through room $c$ (two ways are different if and only if there exists an $i$ such that the $i$-th corridor used is different). Since this number can be very large, output the answer modulo $998244353$.

The first line contains two integers $n, q$, representing the number of nodes and the number of queries. The next $n$ lines each contain two integers $l, r$. The integers $l_i, r_i$ on the $(i+1)$-th line indicate that node $i$ has a directed edge to every node in the interval $[l_i, r_i]$. When $l_i=r_i=0$, it means this node has no outgoing edges. The next $q$ lines each contain four integers $a, b, c, m$, representing one query.

Output $q$ lines. Each line contains one integer. The $i$-th line is the number of ways for the $i$-th query modulo $998244353$.

### Sample Explanation In sample 1, room $1$ can reach rooms $2, 3$. Room $2$ can reach room $1$. Room $3$ can reach rooms $2, 3, 4$. Room $4$ cannot reach any room. For the first query, the ways to go from room $1$ to room $3$ using $5$ corridors and not passing through room $4$ are `121213`, `121333`, `133213`, `132133`, `133333`, totaling five ways. --- ### Constraints **This problem uses bundled testdata.** | ID | Special Property | Memory Limit | Score | | :-: | :-: | :-: | :-: | | 0 | $n\le10$，$q\le10$，$m\le4$ | 256MB | 10pts | | 1 | $n\le100$，$q\le10^4$，$m\le40$ | 256MB | 15pts | | 2 | For all queries, $l_c=r_c=0$ | 256MB | 15pts | | 3 | None | 256MB | 30pts | | 4 | None | 128MB | 30pts | For $100\%$ of the data, $1\le n \le 500$, $1\le q \le 10^5$, $1\le m \le 100$, $0 \le l_i \le r_i \le n$, $1 \le a,b,c \le n$. $r_i=0$ if and only if $l_i=0$. The time limit is 1s for all subtasks. --- ### Hint **Pay attention to the memory constant factors.** Translated by ChatGPT 5