题目描述

给定长度为 $n$ 的正整数序列 $a$，有 $q$ 次询问。对于每次询问，给出 $l,r,k$ 和 $k$ 个限制条件，求有多少个长度为 $n$ 的自然数序列 $b$ 满足 $l\le\sum\limits_{i=1}^na_ib_i\le r$ 且满足这 $k$ 个限制条件，对 $998244353$ 取模。

对于每个限制条件，给出 $x,y$，要求 $b_x=y$。

我们称两个长度为 $n$ 的序列 $b,b'$ 是不同的，当且仅当存在不超过 $n$ 的正整数 $i$ 满足 $b_i\not=b_i'$。

输入格式

输入的第一行包含两个正整数 $n,q$。

第二行包含 $n$ 个正整数 $a_1,a_2,\cdots,a_n$。

接下来有 $q$ 次询问，对于每一次询问：

第一行包含三个非负整数 $l,r,k$。

接下来 $k$ 行，每行两个非负整数 $x,y$，代表一条限制条件。

输出格式

对于每一次询问，输出一行一个整数，表示对应的答案。

4 3
1 10 2 5
10 10 1
3 0
900 910 1
4 2
0 1000 2
2 1
1 5

4
223516
48906

提示

【样例解释】

对于第一次询问，有以下 $4$ 个序列 $b$ 符合条件：$\{0,0,0,2\},\{0,1,0,0\},\{5,0,0,1\},\{10,0,0,0\}$。

序列 $\{3,0,1,1\}$ 不符合条件，因为不满足限制 $b_3=0$；序列 $\{1,1,1,1\}$ 不符合条件，因为不满足 $\sum\limits_{i=1}^na_ib_i=10$。

【数据范围】

本题采用捆绑测试。

子任务编号	特殊性质	分值
$0$	$n,l,r,q\le8$	$10$
$1$	$n,l,r,q\le100$	$15$
$2$	$k=1$ 且 $l=r$	$25$
$3$	$l=r$
$4$	无

对于所有的测试数据，保证：$0\le l,r,y\le5\times10^3$，$1\le n,a_i\le 5\times10^3$，$1\le q\le 5\times 10^4$，$0\le k\le8$，$1\le x\le n$。对于一次询问，保证每一条限制的 $x$ 互不相同。