Problem Description

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

Input Format

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 Format

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

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

1
100000521
1330

Hint

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

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