Five

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 \cdot x_{k+4} + 4 \cdot x_{k+3} + 3 \cdot x_{k+2} + 2 \cdot x_{k+1} + x_{k}$ for each integer $k$.

Note that equality uniquely defines both the positive and negative indices (e.g. $x_5 = 40$, $x_6 = 230$, ... and $x_{-1} = -22$, $x_{-2} = 33$, ...)

Task

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

Input data

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 data

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

Constraints and clarifications

• $1 \leq n \leq 100\ 000$
• $1 \leq q \leq 200\ 000$
• $1 \leq l \leq r \leq n$
• $-M < a_i, value < M$

Example

stdin

1 5
1
1 1 1
2 1 1 -2
1 1 1
2 1 1 8
1 1 1

stdout

1
100000521
1330

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