P16389 [IATI 2024] Five

Due to unforeseen circumstances this task is not fifth. A recent survey by polling agency $\verb|"Ko & co"|$ found that no one likes the numbers from $1$ to $4$. So we will focus on the next number, $5$, and hope it does not follow the unfortunate fate of its predecessors. Consider the following sequence in the positive and negative indices: - $x_0 = 0$ - $x_1 = 1$ - $x_2 = 2$ - $x_3 = 3$ - $x_4 = 4$ - $x_{k+5} = 5 \times x_{k+4} + 4 \times x_{k+3} + 3 \times x_{k+2} + 2 \times x_{k+1} + 1 \times x_{k}$ for each integer $k$. Note that equality uniquely defines both the positive and the negative indices (e.g. $x_5 = 40, x_6 = 230, \dots$ and $x_{-1} = -22, x_{-2} = 33, \dots$) You are given an array of $n$ numbers $a_1, a_2, \dots, a_n$. Write a program $\texttt{five}$ that supports $2$ types of events: - $Query$ with parameters $l, r$. We want to find the value $x_{a_{l}} + x_{a_{l + 1}} + ... + x_{a_{r}} = \sum_{i = l}^{r} x_{a_{i}}$. Since it can get very large, print the answer modulo $M = 10 ^ 8 + 543$. - $Update$ with parameters $l, r, value$. Then the new value of $a_i$ becomes equal to $a_i+value$ for every $l \leq i \leq r$.

The first line of the standard input contains the numbers $n$ and $q$. The next line contains $n$ integers $a_1,a_2,…,a_n$. Each of the following $q$ lines contains $3$ natural numbers $type, l, r$. If $type = 1$, then the line is a $Query$. If $type = 2$, then the line is an $Update$ and contains a further integer $value$.

For each $Query$, print on a new line the answer for that query.

### Sample Explanation At the start $a_1 = 1$ and $x_{a_{1}} = 1$. After the first $Update$ $a_1= -1$ and $x_{a_{1}} = -22$. After the second $Update$ $a_1 = 7$ and $x_{a_{1}} = 1330$. ### Constraints - $1 \leq n \leq 100 000$ - $1 \leq q \leq 200 000$ - $1 \leq l \leq r \leq n$ - $- M < a_i, value < M$ ### Subtasks | **Subtask** | **Points** | **Additional constraints** | | :---: | :---: | :---: | | $1$ | $5$ | $0 \leq a_i \leq 10^6$ and only $Query$ | | $2$ | $19$ | $0 \leq a_i, value$ and $l = r$ | | $3$ | $19$ | $0 \leq a_i, value$ and $q \leq 20 000$ | | $4$ | $19$ | $q \leq 20 000$ | | $5$ | $19$ | $q \leq 100 000$ | | $6$ | $19$ | None | The points for a subtask are given only if all tests for it and the required subtasks are passed successfully.