There are $N$ different types of items. The $i^{th}$ item has $c_i$ distinct copies. In this problem, you are going to deal with $Q$ queries. The $i^{th}$ query is represented by three integers - $l_i, r_i, k_i$. For every query, you need to find the number of ways for choosing $k_i$ items of different types, and their types must be within the interval $[l_i, r_i]$ (inclusive). Since this number might be huge, you are only asked to print its remainder modulo $998244353$.

Note that you can't choose two items of the same type $i$, i.e., if you want to choose an item of type $i$, you can do this in $c_i$ ways.

$\textbf{Input}$

The first line contains two integers - $N$ and $Q$ $(1 \le N,Q \le 2^{14})$.

The next line contains $N$ integers - $c_1, c_2, \dots, c_N (1 \le c_i \le 10^8)$.

The next $Q$ lines contain three integers - $a_i, b_i, k_i$ $(0 \le a_i, b_i < N, 1 \le l_i \le r_i \le N, 1 \le k_i \le r_i - l_i + 1)$. If $last$ is the answer for $(i - 1)^{th}$ (at the beginning $last = 0$) query then:

$1. l_i = ((a_i + last) \mod N) + 1$

$2. r_i = ((b_i + last) \mod N) + 1$

For $25$ points you can consider that $N,Q \le 1024$.

For another $25$ points you can consider that $k_i \le 20$.

For another $25$ points you can consider that $k_i \le 256$.

$\textbf{Output}$

Output $Q$ lines, the $i^{th}$ line constains the answer for the $i^{th}$ query in chronological order.