题目描述

Laura 在 Coolbank 工作时，经常需要处理大量数据，执行一些简单但重复的操作。很自然地，她觉得这些工作不该由人手工完成。可惜她的老板又不愿意花钱请程序员来自动化整个流程。

作为她的好朋友，请你免费帮 Laura 写一个名为 automation 的程序，自动完成这些数据处理工作。

数据表示为一个由 $N$ 个整数组成的序列：

程序会实时接收以下三种类型的操作：

1. 查询下标从 $L$ 到 $R$（含端点）的所有元素之和；
2. 将下标从 $L$ 到 $R$（含端点）的每个元素赋值为给定的 $K$；
3. 将下标从 $L$ 到 $R$（含端点）的每个元素都整除给定的 $K$。

对于每个类型 1 的操作，你都必须返回正确的区间和。

实现细节

你的程序必须实时处理这些操作。

你需要实现如下四个函数：

void init(int subtask, int N, const int A[]);
long long getSum(int L, int R);
void setValues(int L, int R, int K);
void divideValues(int L, int R, int K);

其中：

• init 会在程序开始时被调用一次，且只会调用这一次；
• 传入参数包括：当前测试所属子任务编号 subtask、序列长度 N、初始数组 A；
• 其余三个函数分别对应上面三种操作。

你向系统提交的文件应为 automation.cpp，其中实现上述四个函数。你可以自行编写任意辅助函数、结构体、全局变量等。

但需要满足：

• 文件中不能包含 main 函数；
• 文件开头必须包含头文件：

#include "automation.h"

数据范围

• $0 \le L \le R < N$
• $Q \le 300000$
• $0 \le A_i, K \le 10^9$
• $Q$ 表示单个测试中的操作总数
• 对于每个类型 3 的操作，都保证 $K \ge 2$

子任务与评分

只有通过某一子任务中的全部测试点，才能获得该子任务的分数。

本地测试

题目提供 automation.h 和 Lgrader.cpp，你可以把它们与你的程序一起编译，以便进行本地测试。

Lgrader 的输入格式如下：

• 第一行输入一个整数 $1$ 到 $6$，表示测试所属子任务编号；
• 第二行输入 $N,Q$，表示序列长度和操作总数；
• 第三行输入 $N$ 个整数，表示初始值；
• 接下来 $Q$ 行，每行是一条操作，格式为以下之一：

1 L R
2 L R K
3 L R K

你可以对提供的文件进行任意修改。

样例

输入

1
5 6
7 0 5 4 2
1 1 3
2 2 4 8
3 1 4 3
1 0 4
3 0 1 100
1 0 1

输出

9
13
0

说明

给出的样例输入采用的是 Lgrader.cpp 所使用的输入格式；输出对应于你的 getSum 函数返回的值。你的程序不应该从标准输入读入，也不应该向标准输出写出。

该测试属于子任务 1，包含 $N=5$ 个数、$Q=6$ 个操作。初始序列为：

7 0 5 4 2

• 第 1 个操作查询下标 $1$ 到 $3$ 的区间和，答案为 $0+5+4=9$；
• 第 2 个操作后，下标 $2$ 到 $4$ 的元素都变为 $8$，此时序列为：

7 0 8 8 8

• 第 3 个操作后，下标 $1$ 到 $4$ 的元素都整除 $3$，此时序列为：

7 0 2 2 2

• 第 4 个操作查询整个区间，答案为 $7+0+2+2+2=13$；
• 第 5 个操作后，下标 $0$ 到 $1$ 的元素都整除 $100$，此时序列为：

0 0 2 2 2

• 第 6 个操作查询下标 $0$ 到 $1$ 的区间和，答案为 $0+0=0$。