Arithmetic Sequence and Queries

Time limit2sMemory limit512 MB

Summary

Given an arithmetic sequence with first term a and difference d, answer queries for the sum or the gcd of a contiguous range of terms.

Level: Medium6 of 10
Topics: Math, Number theory, Prefix sum, Implementation
Solved: No attempts yet

Problem

An arithmetic sequence is a sequence in which the difference between consecutive terms is constant. For two consecutive terms, the value obtained by subtracting the earlier term from the later term is called the common difference. You are given an arithmetic sequence whose first term is $a$ and whose common difference is $d$ . Let $A_i$ be the $i$ -th element of the sequence. Write a program that processes the following queries.

1 l r : Print the sum of $A_l, A_{l+1}, ... , A_r$ .
2 l r : Print the greatest common divisor of $A_l, A_{l+1}, ... , A_r$ . This is the largest positive integer among the common divisors of $A_l, A_{l+1}, ... , A_r$ .

Input

The first line gives the first term $a$ and the common difference $d$ of the sequence.

The second line gives the number of queries $q$ .

Each of the next $q$ lines gives one query.

Output

For each query, print the answer on its own line.

Constraints

$1 ≤ a ≤ 10^6$ , $0 ≤ d ≤ 10^6$
$1 ≤ q ≤ 10^6$
$1 ≤ l ≤ r ≤ 10^6$

Examples2

Example 1
Input
```
4 2
3
1 1 1
1 1 2
2 1 2
```
Expected output
```
4
10
2
```
Example 2
Input
```
5 3
2
1 2 5
2 3 6
```
Expected output
```
50
1
```