题目背景

光芒浸透圣巢，她正犯下弥天之错。

所剩寥寥无几的信仰，为什么始终执着。

我将作灯塔，照耀王国。

但在那之前有更重要的事去做，

无论什么代价都在所不惜，尽管我所剩无多……

题目描述

白王正在最后一次参观他建造的宏伟宫殿。现在假设宫殿由 $n$ 个房间构成，房间之间有若干个单向通道。出于白王奇怪的装修癖好（不是指到处安电锯），对于第 $i$ 个房间，它向编号在区间 $[l_i,r_i]$ 中的所有房间都连有一条单向通道。例如，$4$ 号房间向 $[2,5]$ 连有单向通道，就意味着从 $4$ 号房间到 $2,3,4,5$ 号房间各有一条单向通道（一个房间可以向自己连有通道）。当一个房间向 $[0,0]$ 连有通道时，表示没有从这个房间出发的通道。

白王提出了 $q$ 个问题，每次询问从 $a$ 号房间，通过恰好 $m$ 条单向通道且不经过 $c$ 号房间到达 $b$ 号房间的方案数（两方案不同，当且仅当存在 $i$ 使得两方案通过的第 $i$ 条通道不同）。因为这个数字可能会很大，所以白王让你将答案模 $998244353$ 后再回答。

输入格式

第一行，两个整数 $n, q$ 表示点数和询问数。

接下来 $n$ 行，每行两个整数 $l, r$，第 $i+1$ 行的整数 $l_i, r_i$ 表示 $i$ 号节点向区间 $[l_i, r_i]$ 中的每个点都连了一条单向边。当 $l_i=r_i=0$ 时，表示该节点没有向任何点连边。

接下来 $q$ 行，每行四个整数 $a, b, c, m$ 表示一个询问。

输出格式

$q$ 行，每行一个整数，第 $i$ 行的数字表示第 $i$ 个询问的方案数模 $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

提示

样例说明

在样例一中，$1$ 号房间能到达 $2,3$ 号房间，$2$ 号房间能到达 $1$ 号房间，$3$ 号房间能到达 $2,3,4$ 号房间，$4$ 号房间不能到达任何房间。

对于第一个询问，从 $1$ 号房间经过 $5$ 条通道且不经过 $4$ 号房间到达 $3$ 号房间的方案有 121213，121333，133213，132133，133333 共五种。

数据范围

本题采用捆绑测试。

对于 $100\%$ 的数据，$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$。当且仅当 $l_i=0$ 时 $r_i=0$。时间限制均为 1s。

提示

注意空间常数。