通常，每当 Akulyat 遇到涉及查询和神秘操作的问题时，他都会立即将其委托给 KiKoS。为了在 Pafos 训练营期间教育 Akulyat，KiKoS 决定给他这道题。但是，好吧，计划失败了：Akulyat 找到了大海，并把所有时间都花在了那里。不过，至少现在有一道未解决的问题留给你了。

给你一个由 $n$ 个正整数组成的数组 $a = [a_1, a_2, \dots, a_n]$。

我们定义 $f_k(b_1, b_2, \dots, b_m)$ 为对数组 $[b_1, \dots, b_m]$ 最多执行 $k$ 次以下操作后，该数组元素乘积的最小可能值：

• 选择任意满足 $b_i > 1$ 的下标 $i$，并令 $b_i := b_i - 1$。

你的任务是处理 $q$ 次查询。每次查询由三个整数 $\ell$、$r$ 和 $k$ 给出，要求你计算 $f_k(a_\ell, a_{\ell+1}, \dots, a_r)$ 的值：即对子数组 $a_\ell$ 到 $a_r$ 最多执行 $k$ 次上述操作后，该子数组元素的最小可能乘积。

由于答案可能很大，请将结果对 $998\,244\,353$ 取模后输出。

输入格式

第一行包含两个整数 $n$ 和 $q$（$1 \le n \le 2 \cdot 10^5$，$1 \le q \le 5 \cdot 10^5$），分别表示数组的大小和查询的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 998\,244\,352$）。

接下来的 $q$ 行，每行包含三个整数 $\ell$、$r$ 和 $k$（$1 \le \ell \le r \le n$，$0 \le k \le 10^{18}$），描述一次对下标从 $\ell$ 到 $r$ 的子数组进行最多允许 $k$ 次操作的查询。

输出格式

对于每次查询，输出一个整数：$f_k(a_\ell, \dots, a_r)$ 对 $998\,244\,353$ 取模后的值。

样例

输入样例 1

5 2
1 2 3 4 5
1 2 3
4 5 1

输出样例 1

1
15

说明

乘积是在应用所有操作之后计算的，只有最终结果才需要对 $998\,244\,353$ 取模。