You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

我有仁义礼智信 啥子都搞得定

我的歌 不在酒吧放 我送给老百姓

我有仁义礼智信 我讲话你要听

你来惹我丢的不是钱 丢的那是命

题目描述

茶楼里各式各样的茶让小f目不暇接，没事的时候他就会来茶楼喝茶。

慢慢的小f长大了该谈恋爱了，虽然茶楼明显不是约会的好去处，但是小f每次都会带他的女朋友去茶楼一起喝茶。

茶楼里有 $n$ 种茶， 第 $i$ 种茶的价格是 $x$ 元， 小f每次都会带 $m$ 元钱来茶楼里面喝茶。小f有强迫症，每次都要把手里的 $m$ 元钱花完才甘心。

小f的女朋友口味又很刁钻且每次来茶楼都不一样。他们会来 $q$ 次茶楼，第 $i$ 次来茶楼的时候，由于宇宙射线的原因，小f的女朋友不会喜欢喝第 $x$ 种茶，如果小f点了第 $x$ 种茶，那么小f会痛失女朋友。

另外小f还有自己的想法，第 $i$ 次来茶楼的时候，他想喝到至少一杯第 $y$ 种茶，但是如果这个想法和女朋友的冲突了，那么他会选择听女朋友的。

现在小f想问你，每次他们来茶楼的时候，符合小f和他女朋友的想法并且把手上的钱都花完的点茶方案有多少种？求出对 $998244853$ 取模的结果。

输入格式

第一行两个数 $n,m$，表示茶楼中茶的种类和小f带的钱。

接下来一行 $n$ 个整数，表示每种茶的价格。

接下来一行一个整数 $q$，表示小f和他女朋友来茶楼的次数。

接下来 $q$ 行每行两个整数 $x,y$，表示这一次小f女朋友不想喝 $x$ 这种茶，小f想要喝到至少一杯 $y$ 这种茶。

输出格式

$q$ 行，对于每次询问，输出答案对 $998244853$ 取模的结果。

3 10
3 3 4
2
1 3
2 3

1
1

数据规模与约定

对于 $100\%$ 的数据，$1 \le 题面中所有数字\le 10^4$。