다섯

예상치 못한 사정으로 이 문제는 다섯 번째가 아니다.

여론조사 기관 "Ko & co"가 최근 실시한 설문에서 1부터 4까지의 숫자를 좋아하는 사람이 없다는 결과가 나왔다. 그래서 다음 숫자인 $5$에 집중하고, 이 숫자는 앞선 숫자들과 같은 불운을 겪지 않기를 바란다.

양의 인덱스와 음의 인덱스를 모두 갖는 다음 수열을 생각하자.

• $x_0 = 0$
• $x_1 = 1$
• $x_2 = 2$
• $x_3 = 3$
• $x_4 = 4$
• 모든 정수 $k$에 대해 $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$

이 등식은 양의 인덱스와 음의 인덱스의 값을 유일하게 정한다. 예를 들어 $x_5 = 40$, $x_6 = 230$이고, $x_{-1} = -22$, $x_{-2} = 33$이다.

$n$개의 수로 이루어진 배열 $a_1, a_2, \dots, a_n$이 주어진다. 다음 두 종류의 이벤트를 처리하는 프로그램 five를 작성하라.

• 매개변수 $l$, $r$을 받는 Query. $\sum_{i=l}^r x_{a_i}$를 구한다. 값이 매우 커질 수 있으므로, 답을 $M = 10^8 + 543$으로 나눈 나머지를 출력한다.
• 매개변수 $l$, $r$, $value$를 받는 Update. 모든 $l \le i \le r$에 대해 $a_i$의 값을 $a_i + value$로 바꾼다.

첫 줄에 $n$과 $q$가 주어진다. 다음 줄에는 $n$개의 정수 $a_1, a_2, \dots, a_n$이 주어진다. 이어지는 $q$개의 줄에는 각각 세 개의 자연수 $type$, $l$, $r$이 주어진다.

• $type = 1$이면 해당 줄은 Query이다.
• $type = 2$이면 해당 줄은 Update이며, 정수 $value$가 하나 더 주어진다.

Query마다 답을 한 줄에 출력한다.

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

시간 제한은 700 ms, 메모리 제한은 1024 MB이다.