共有$$$n$$$袋,编号从$$$1$$$到$$$n$$$,第$$$i$$$袋包含$$$a_i$$$金币和$$$b_i$$$银币。
金币的价值为 $$$1$$$。银币的价值为 $$$0$$$ 或 $$$1$$$,由每枚银币独立确定($$$0$$$ 的概率为 $$$\frac{1}{2}$$$,$$$1$$$ 的概率为 $$$\frac{1}{2}$$$)。
您必须回答 $$$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$$$) — 第 $$$i$$$ 袋中的金币数量。
第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$0 \le b_i \le 10^6$$$) — 第 $$$i$$$ 袋中的银币数量。
接下来的 $$$q$$$ 行包含查询。接下来的 $$$q$$$ 行的第 $$$j$$$ 行包含两个整数 $$$l_j$$$ 和 $$$r_j$$$ ($$$1 \le l_j \le r_j \le n$$$) — 第 $$$j$$$ 查询的描述。
输入的附加限制:
- 数组$$$a$$$的总和不超过$$$10^6$$$;
- 数组 $$$b$$$ 的总和不超过 $$$10^6$$$。
输出
对于每个查询,打印一个整数 - 从 $$$l$$$ 到 $$$r$$$ 的袋子中的硬币总价值严格大于所有其他袋子中的总价值的概率,以 $$$998244353$$$ 为模。
形式上,概率可以表示为不可约分数 $$$\frac{x}{y}$$$。您必须打印 $$$x \cdot y^{-1} \bmod 998244353$$$ 的值,其中 $$$y^{-1}$$$ 是一个整数,使得 $$$y \cdot y^{-1} \bmod 998244353 = 1$$$。
示例
输入 #1
2 2 1 0 0 2 2 2 1 1
输出 #1
748683265 748683265
输入 #2
4 3 2 3 4 5 1 0 7 3 3 3 2 3 1 4
输出 #2
997756929 273932289 1
注意
在第一个示例的两个查询中,答案都是 $$$\frac{1}{4}$$$。