## Algorithm

Problem Name: beecrowd | 3306

# Search and Change

By Abner Samuel P. Palmeira, Instituto Federal do Sul de Minas Gerais Brazil

Timelimit: 1

Given a vector with N elements, answer Q queries of types:

1 A B V: Add V across all elements from position A to position B of the vector.

2 A B: Returns the Greatest Common Divisor of all elements from positions A to B in the vector

## Input

The input consists of several test cases. The first line of each test case contains two integers N Q, representing respectively the vector size and the number of queries. The second line of input contains N integers representing the elements of the vector. The next Q lines contain the queries as described above.

Limits:

1 ≤ N; Q ≤ 105

## Output

For each type 2 query print the GCD of all vector positions that are in the AB range

 Input Samples Output Samples 7 4 1 8 4 16 6 13 20 2 2 4 2 5 7 1 5 7 1 2 5 7 4 1 7

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const { readFileSync } = require("node:fs")

.trimEnd() // Prevent EOF
.split(/\s+/g)
.map(value => Number.parseInt(value, 10))

//// MATH ////

const MyMath = Object.create(Math, {
gcd: {
/**
* @param {number} x
* @param {number} y
*/
value: function gcd(x, y) {
if (isNaN(x) || isNaN(y)) return Number.NaN
x = Math.abs(x)
y = Math.abs(y)
while (y) [x, y] = [y, x % y]
return x
},
configurable: false,
enumerable: false,
writable: false
}
})

// //// MAIN ////

async function main() {
const output = []

while (input.length > 0) {
const [N, Q] = input.splice(0, 2)
const elements = input.splice(0, N)

for (let q = 1; q  < = Q; q += 1) {
const [C, A, B] = input.splice(0, 3)

if (C == 1) {
const V = input.shift()
for (let index = A - 1; index  <  B; index += 1)
elements[index] += V
} else if (C == 2) {
let gcd = elements[A - 1]
for (let index = A; index  <  B; index += 1)
gcd = MyMath.gcd(gcd, elements[index])
output.push(gcd)
} else { output.push(q) }
}
}

console.log(output.join("\n"))
}

main()

``````
Copy The Code &

Input

cmd
7 4 1 8 4 16 6 13 20 2 2 4 2 5 7 1 5 7 1 2 5 7

Output

cmd
4 1 7