题目描述

民调机构 “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*x_{k+4} + 4*x_{k+3} + 3*x_{k+2} + 2*x_{k+1} + x_k

注意，这个等式会唯一确定所有正下标和负下标处的值。例如：

• x_5 = 40
• x_6 = 230
• x_{-1} = -22
• x_{-2} = 33

给定一个长度为 n 的数组 a_1, a_2, ..., a_n，你需要支持两类操作：

• 查询 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 <= i <= r，令

a_i = a_i + value

输入格式

• 第 1 行：两个整数 n, q；
• 第 2 行：n 个整数 a_1, a_2, ..., a_n；
• 接下来 q 行：
  • 每行先给出三个整数 type, l, r；
  • 若 type = 1，表示一次查询；
  • 若 type = 2，则该行还会再给出一个整数 value，表示一次区间加法修改。

输出格式

对于每次查询，输出一行答案。

约束条件

• 1 <= n <= 100000
• 1 <= q <= 200000
• 1 <= l <= r <= n
• -M < a_i, value < M

子任务

只有当某个子任务以及它要求的前置子任务全部通过时，才能获得该子任务的分数。

样例

输入

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。