Paths in the Forbidden Room Palace

The White King is making his final tour of the grand palace he built. The palace consists of \(n\) rooms with several directed passages between them. For each room \(i\), there is a directed passage from room \(i\) to every room in the interval \([l_i,r_i]\). Note that a room may have a passage to itself. If a room has a passage to \([0,0]\), it means that room has no outgoing passage.

The White King has \(q\) queries. Each query asks: given a starting room \(a\), a destination room \(b\), and an integer \(m\), find the number of distinct paths from \(a\) to \(b\) that use exactly \(m\) passages and never visit room \(c\) (the forbidden room). Two paths are considered different if there exists an index \(i\) such that the \(i\)th passage in each path is different.

Since the answer can be very large, output it modulo \(998244353\).

inputFormat

The first line contains two integers \(n\) and \(q\) \( (1 \le n, q)\), representing the number of rooms and the number of queries.

The following \(n\) lines each contain two integers \(l_i\) and \(r_i\) for \(i = 1, 2, \ldots, n\). For room \(i\), there is a directed passage to every room in the interval \([l_i,r_i]\). If \(l_i = r_i = 0\), then room \(i\) has no outgoing passage.

Each of the next \(q\) lines contains four integers \(a, b, m, c\):

• \(a\): the starting room,
• \(b\): the destination room,
• \(m\): the exact number of passages to be used,
• \(c\): the forbidden room which must not be visited (including the starting room).

outputFormat

For each query, output a single line containing one integer — the number of valid paths modulo \(998244353\).

sample

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

1
0
0