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 \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 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}} + \dots + 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 ≤ i ≤ r$.

The first line of the standard input contains the numbers $n$ and $q$. The next line contains $n$ integers $a_1, a_2 ,\dots , 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.

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