题目描述

给定一个长度为 n 的数列 v_1, v_2, ..., v_n。你需要回答如下询问：

给定整数 a, b, c, l, r，求：

gcd(f(v_l), f(v_{l+1}), ..., f(v_r))

其中：

f(x) = a * x^2 + b * x + c

请编写程序 gcdSquared 来回答这些询问。

实现要求

这是一个提交函数题。

你提交的程序必须包含如下函数：

void init(int n, const int v[]);
long long getGCD(int a, int b, int c, int l, int r);

• init 会在程序开始时且在任何询问之前被调用恰好一次，参数为数列长度 n 和数列内容 v；
• 随后会有 q 次对 getGCD 的调用，参数含义与题目描述一致；
• 你需要提交文件 gcdSquared.cpp，其中实现上述两个函数；
• 你可以自由添加辅助函数、结构体、变量等；
• 提交文件中不能包含 main 函数；
• 提交文件开头必须包含头文件：

#include "gcdSquared.h"

数据范围

• 1 <= n, q <= 200000
• 1 <= l <= r <= n
• 1 <= v_i <= 10^6
• 0 <= a, b, c <= 10^6 且 a + b + c > 0

子任务

一项子任务只有在该子任务下所有测试全部通过时，才能获得该子任务的分数。

本地测试

题目提供了文件 gcdSquared.cpp 和 Lgrader.cpp，你可以将它们与自己的程序一同编译进行本地测试。

Lgrader.cpp 的输入格式如下：

第一行输入 n 和 q。
第二行输入 n 个整数 v_1, v_2, ..., v_n。
接下来 q 行，每行输入五个整数 a, b, c, l, r。

原题还说明：你可以按需要自行修改所提供的本地测试文件。

样例

输入

5 1
1 2 3 4 5
1 2 3 4 5

输出

1

样例解释

f(v_4) = 1 * 4^2 + 2 * 4 + 3 = 27，f(v_5) = 1 * 5^2 + 2 * 5 + 3 = 38，因此

gcd(27, 38) = 1。