Alice 和 Bob 在一个长度为 $N$ 的整数数组 $A$ 上进行游戏。Alice 选择一个秘密下标 $i$，Bob 选择一个秘密下标 $j$。如果 $i = j$，则 Alice 获得 $A_i$ 分，否则她获得 $0$ 分。随后游戏结束。

Alice 希望最大化得分，而 Bob 希望最小化得分。双方都会选择各自的策略，使得即使策略被对方获知，也无法被利用。

请回答 $Q$ 个询问，每个询问给定一个元组 $[L, R, K]$。对于每个询问：

• 游戏将在子数组 $A_L, A_{L+1}, \dots, A_R$ 上进行。

• 玩家的策略是一个概率分布 $P_L, P_{L+1}, \dots, P_R$（满足 $\sum_{i=L}^R P_i = 1, 0 \le P_i \le 1$），这意味着玩家将以概率 $P_i$ 选择下标 $i$。

• 在游戏开始前，Alice 最多可以执行 $K$ 次增加操作。一次增加操作是指对某个 $i \in [L, R]$ 执行 $A_i = A_i + 1$。该操作可以对同一个 $i$ 执行多次。增加操作仅影响当前询问，不会对后续询问产生影响。

请输出每个询问中 Alice 获得分数的期望值。答案可以表示为不可约分数 $\frac{X}{Y}, Y \neq 0$。你需要输出 $(X \cdot Y^{-1}) \pmod{998244353}$ 的值。保证对于每个询问，答案均可计算（即 $Y^{-1}$ 在模 $998244353$ 下存在）。

输入格式

第一行包含一个整数 $N(1 \le N \le 2 \cdot 10^5)$。第二行包含 $N$ 个空格分隔的整数 $A_1, A_2, \dots, A_N(1 \le A_i \le 10^8)$。第三行包含一个整数 $Q(1 \le Q \le 10^5)$，表示询问次数。 接下来的 $Q$ 行，每行包含 3 个整数 $L_i, R_i, K_i(1 \le L_i \le R_i \le N, 0 \le K_i \le 10^8)$，表示第 $i$ 个询问。

输出格式

对于每个询问，在单独的一行中输出答案。

样例

输入格式 1

3
1 2 3
3
1 3 3
1 1 6
1 2 2

输出格式 1

2
0
598946613