题目背景

晴天娃娃晴娃娃，明天求你要放晴，

如果依我愿望做，给你甜酒喝个够。

晴天娃娃晴娃娃，明天求你要放晴，

如果雨还哭啼啼，就把你头切落地。

题目描述

给出 $n$ 个修改，每种修改写做一个二元组 $(x_i,y_i)$ ，$x_i=0$ 时表示区间 $+y_i$ ，$x_i=1$ 时表示区间 $\times y_i$ 。

接下来对一个初始全零，长度为 $n$ 的序列做 $m$ 次操作，每次操作给出 $l_1,r_1,l_2,r_2$ ，对区间 $[l_1,r_1]$ 依次做下标在 $[l_2,r_2]$ 之间的修改。并且输出做完所有修改后，$[l_1,r_1]$ 区间内所有数的和。

以上所有修改和求和皆在模 $998244353$ 意义下进行。

输入格式

第一行输入 $n,m$ 。

接下来 $n$ 行，每行一组 $x,y$ 表示一种修改。

接下来 $m$ 行，每行一个 $l_1,r_1,l_2,r_2$，表示一个操作。

输出格式

输出 $m$ 个操作的结果。每行一个。

样例 #1

样例输入 #1

3 3
0 2
0 2
1 1
3 3 1 1
2 3 1 3
1 3 2 2

样例输出 #1

2
10
16

提示

对于 $20\%$ 的数据，$n,m \le 20$

对于另外 $10\%$ 的数据，只有加一种修改。

对于所有数据，$n,m \le 2 \cdot 10^5$，$x \in \left \{ 0,1 \right \}$，$y \le10^8$，$1\le l_i\le r_i \le n$