five — IATI senior
Task type: batch | Time limit: 0.7 s | Memory limit: 256 MB | Difficulty: 25
Algorithms: segment tree, fast exponentiation, linear algebra

![][0]

**Task A3. Five** 0.7 sec. 256 MB

*Due to unforeseen circumstances this task is not fifth.*

A recent survey by polling agency "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 * x_{k+4} + 4 * x_{k+3} + 3 * x_{k+2} + 2 * x_{k+1} + 1 * 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$, ... and $x_{-1} = -22$, $x_{-2} = 33$, ...)

You are given an array of $n$ numbers $a_1, a_2, ..., a_n$. Write a program **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 \le i \le r$.

#### Input

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$.

#### Output

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

![][1]

#### Constraints

• $1 \le n \le 100000$
• $1 \le q \le 200000$
• $1 \le l \le r \le n$
• $-M < a_i, value < M$

#### Subtasks

| Subtask | Points | Additional constraints |
|---|---|---|
| 1 | 5 | $0 \le a_i \le 10^6$ and only *Query* |
| 2 | 19 | $0 \le a_i, value$ and $l = r$ |
| 3 | 19 | $0 \le a_i, value$ and $q \le 20000$ |
| 4 | 19 | $q \le 20000$ |
| 5 | 19 | $q \le 100000$ |
| 6 | 19 | None |

*The points for a subtask are given only if all tests for it and the required subtasks are passed successfully.*

#### Example

| Input | Output | Explanation |
|---|---|---|
| 1 5<br>1<br>1 1 1<br>2 1 1 -2<br>1 1 1<br>2 1 1 8<br>1 1 1 | 1<br>100000521<br>1330 | 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$. |

[0]: _page_0_Picture_1.jpeg
[1]: _page_1_Picture_1.jpeg

Starter code: