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.