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.