题目描述

由于不可预见的情况，本题并非第五题。

一家名为“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$，$\dots$ 以及 $x_{-1} = -22$，$x_{-2} = 33$，$\dots$）。

给定一个包含 $n$ 个数的数组 $a_1, a_2, \dots, a_n$。请编写一个程序 $\texttt{five}$，支持以下 $2$ 种操作：

• 查询：给定参数 $l, r$，求 $x_{a_{l}} + x_{a_{l + 1}} + ... + x_{a_{r}} = \sum_{i = l}^{r} x_{a_{i}}$。由于答案可能非常大，请输出其对 $M = 10 ^ 8 + 543$ 取模的结果。
• 更新：给定参数 $l, r, value$，则对于每个 $l \leq i \leq r$，$a_i$ 的新值变为 $a_i + value$。

输入格式

第一行包含两个整数 $n$ 和 $q$。

接下来一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$。接下来的 $q$ 行，每行包含三个整数 $type, l, r$。

若 $type = 1$，则该行为一个查询。

若 $type = 2$，则该行为一个更新，并额外包含一个整数 $value$。

输出格式

对于每个查询，在新的一行输出该查询的答案。

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

1
100000521
1330

提示

样例解释

初始时 $a_1 = 1$，$x_{a_{1}} = 1$。第一次更新后 $a_1 = -1$，$x_{a_{1}} = -22$。第二次更新后 $a_1 = 7$，$x_{a_{1}} = 1330$。

数据范围

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

子任务

只有当某个子任务的所有测试数据及其所依赖子任务的全部测试数据均成功通过时，该子任务的分数才会被给出。

翻译由 DeepSeek V4 Pro 完成