Problem Background

The light permeates the sacred nest, and she is committing a grave mistake.

The remaining faith is scarce, yet why is it so persistent?

I will be the lighthouse, illuminating the kingdom.

But before that, there are more important things to do,

No matter the cost, it must be done, even though I have little left...

Problem Description

The White King is making his final tour of the magnificent palace he built. Assume the palace consists of $n$ rooms connected by several one-way passages. Due to the White King's peculiar decorating habits (not referring to installing buzzsaws everywhere), for the $i$-th room, it has one-way passages to all rooms whose numbers are within the interval $[l_i, r_i]$. For example, if room $4$ has passages to $[2, 5]$, it means there are one-way passages from room $4$ to rooms $2, 3, 4, 5$ (a room can have a passage to itself). When a room has passages to $[0, 0]$, it indicates there are no outgoing passages from that room.

The White King poses $q$ questions, each asking for the number of ways to reach room $b$ from room $a$ by exactly $m$ one-way passages without passing through room $c$ (two plans are considered different if there exists an $i$ such that the $i$-th passage taken is different). Since this number could be very large, the White King asks you to output the answer modulo $998244353$.

Input Format

The first line contains two integers $n$ and $q$, representing the number of rooms and the number of queries, respectively.

The next $n$ lines each contain two integers $l$ and $r$. The $(i+1)$-th line's integers $l_i$ and $r_i$ indicate that the $i$-th room has one-way passages to every room in the interval $[l_i, r_i]$. When $l_i = r_i = 0$, it means the room has no outgoing passages.

The next $q$ lines each contain four integers $a$, $b$, $c$, and $m$, representing a query.

Output Format

Output $q$ lines, each containing one integer. The $i$-th line's number represents the result of the $i$-th query modulo $998244353$.

Sample Input and Output

Input Sample #1

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

Output Sample #1

5
1
0
1
1

Input Sample #2

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

Output Sample #2

0
17
2
0
0
46
0
12
23
1

Input Sample #3

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

Output Sample #3

0
17
1
0
0
0
1
1
4
1

Notes

Sample Explanation

In the first sample, room $1$ can reach rooms $2$ and $3$, room $2$ can reach room $1$, room $3$ can reach rooms $2$, $3$, and $4$, and room $4$ cannot reach any room.

For the first query, the ways to reach room $3$ from room $1$ through $5$ passages without passing through room $4$ are 121213, 121333, 133213, 132133, 133333, totaling five ways.

Data Range

This problem uses subtask testing.

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$. When $l_i = 0$, $r_i = 0$. The time limit is 1 second.

Hints

Be mindful of space constants.

见题面 Input 部分

见题面 Output 部分