Background

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...

Problem Description

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$.

Input Format

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 Format

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

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

5
1
0
1
1

10 10
6 6
4 10
2 5
1 7
3 4
5 7
4 10
1 7
1 3
2 5
8 8 5 1
4 7 5 3
5 9 4 4
1 5 5 2
6 2 10 2
3 3 7 4
1 10 1 2
6 2 4 4
9 2 1 4
9 10 3 2

0
17
2
0
0
46
0
12
23
1

10 10
2 6
6 9
5 7
3 9
0 0
0 0
3 5
5 5
3 6
1 10
5 9 6 3
10 8 6 4
10 8 5 1
8 6 5 4
7 2 5 4
6 1 5 3
10 4 5 1
5 5 6 0
7 9 6 4
4 9 6 2

0
17
1
0
0
0
1
1
4
1

Hint

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.

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