Competitions

# 2019 Fall KBTU OPEN

# Boring GCD

You are given an array `a`

, _{1}`a`

, _{2}`a`

, ..., _{3}`a`

. There are _{n}**4** types of operations with it:

**l r x**, for each**i**∈ [**l**,**r**] replace`a`

with the value of_{i}**x**;**2 l r x**, for each**i**∈ [**l**,**r**] replace`a`

with the value of_{i}**gcd**(`a`

,_{i}**x**) function;**3 l r**, output the value of**max**`a`

,_{i}**l**≤**i**≤**r**;**4 l r**, output the value of`a`

+_{l}`a`

+ ... +_{l+1}`a`

;_{r}

Greatest common divisor **gcd**(**a**, **b**) of two positive integers **a** and **b** is equal to the biggest integer **d** such that both integers **a** and **b** are divisible by **d**.

#### Input

The first line contains two integers **n**, **q** (**1** ≤ **n**, **m** ≤ `10`

) - the number of array elements and the number of queries.^{5}

The second line contains **n** positive integers `a`

, _{1}`a`

, ..., _{2}`a`

- initial state of the array._{n}

Next **m** lines contain the description of the queries, one per line. Queries are formatted the same way as in the problem statement above.

It is guaranteed that **1** ≤ **l** ≤ **r** ≤ **n** and **1** ≤ **x** ≤ `10`

.^{9}

#### Output

For each **3**-rd and **4**-th query type output answer for this query in a separate line.

Input example #1

5 11 1 6 8 7 3 3 1 5 4 1 5 2 1 5 6 3 1 5 4 2 4 1 1 5 10 3 1 4 4 3 5 2 3 4 3 3 2 3 4 4 5

Output example #1

8 25 6 9 10 30 10 11