题目描述

波奇酱在幻想中得到一组长度为 $n$ 的整数序列 ${a}$ 以及 $q$ 次询问。

每次询问都会给定两个整数 $l,r$ ，表示波奇酱将会在子段 ${a_l,a_{l+1},\ldots,a_r}$ 中进行操作，而波奇酱的操作如下：

每次从子段中随机选择两个数（不妨记为 $a_i,a_j$），将两数从子段中移除并将两数的平均数 $\frac{a_i+a_j}{2}$ 放入到子段中。当子段中只存在一个数时，停止操作，并记最后一个数为 $x$ ，波奇酱好奇 $x$ 的期望是多少，你能帮助他求出来吗？

每次询问都是独立的，换句话来说，每次询问操作都不会改变原序列。

输入格式

第一行输入两个整数 $n,q (1 \leq n,q \leq 2 \times 10^5)$ ，代表整数序列的长度以及询问次数。

第二行输入 $n$ 个整数，第 $i$ 个整数代表 $a_i (1 \leq a_i \leq 10^9)$。

接下来 $q$ 行，每行两个整数 $l,r(1 \leq l \leq r \leq n)$ ，代表波奇酱此次询问的操作目标子段为 $a_l,a_{l+1},\ldots,a_r$。

输出格式

输出 $q$ 行，每行包含一个整数，表示子段最后一个整数的期望，答案对 $998244353$ 取模。

输入输出样例 #1

输入 #1

5 1
1 2 3 4 5
2 5

输出 #1

499122180

说明/提示

不妨令 $m=998244353$ ，可以证明，本题答案一定可以表示为一个既约分数 $\frac{p}{q}$ ，其中 $p,q$ 均为整数且 $q \not \equiv 0 \pmod{m}$ 。你需要找到一个这样的整数 $x(0 \leq x < m)$ ，使得 $x \times q \equiv p \pmod{m}$。