F. 稀有硬币

单个测试点时间限制：$2$ 秒 单个测试点内存限制：$256$ 兆字节

有 $n$ 个袋子，编号为 $1$ 到 $n$。第 $i$ 个袋子中有 $a_i$ 枚金币和 $b_i$ 枚银币。

• 每枚金币的价值固定为 $1$。
• 每枚银币的价值独立随机为 $0$ 或 $1$：取 $0$ 的概率为 $\dfrac12$，取 $1$ 的概率为 $\dfrac12$。

你需要回答 $q$ 个相互独立的询问。每个询问如下：

给定 $l,r$，计算编号从 $l$ 到 $r$ 的袋子中硬币总价值严格大于其余所有袋子总价值的概率。

---

输入格式

第一行包含两个整数 $n$ 和 $q$（$1\le n,q\le 3\cdot 10^5$），分别表示袋子数和询问数。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$（$0\le a_i\le 10^6$），表示每个袋子中的金币数量。

第三行包含 $n$ 个整数 $b_1,b_2,\dots,b_n$（$0\le b_i\le 10^6$），表示每个袋子中的银币数量。

接下来 $q$ 行，每行两个整数 $l_j,r_j$（$1\le l_j\le r_j\le n$），表示第 $j$ 个询问。

额外约束：

• 数组 $a$ 的总和不超过 $10^6$；
• 数组 $b$ 的总和不超过 $10^6$。

---

输出格式

对每个询问输出一个整数，表示所求概率对 $998244353$ 取模的结果。

形式化地说，概率可以表示为既约分数 $\dfrac{x}{y}$，你需要输出

$$x\cdot y^{-1} \bmod 998244353$$

其中 $y^{-1}$ 是满足 $y\cdot y^{-1}\equiv 1 \pmod{998244353}$ 的整数。

---

样例输入

2 2
1 0
0 2
2 2
1 1

样例输出

748683265 748683265

第二个样例输入

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

第二个样例输出

997756929 273932289 1

---

说明

第一个样例的两次询问答案都是 $\dfrac14$。