Միջակայքի GCD (Մեծագույն ընդհանուր բաժանարար) հարցումներ

Ձեզ տրված է n էլեմենտ ունեցող զանգված և q հարցում։ Հարցումները երկու տեսակ են. կամ պետք է հաշվել GCD-ը (Մեծագույն ընդհանուր բաժանարարը) նշված միջակայքի համար, կամ պետք է թարմացնել զանգվածի որևէ էլեմենտ։ Ձեր նպատակը արդյունավետ կերպով մշակել այս հարցումները։

Մուտք

Մուտքի առաջին տողում տրված են երկու ամբողջ թվեր n և q (1 ≤ n, q ≤ 100 000), որոնք նշում են, թե քանի էլեմենտ ունի զանգվածը և քանի հարցում կա համապատասխանաբար։

Մուտքի երկրորդ տողում տրված են n թվեր (), որոնք կազմում են զանգվածի նախնական էլեմենտները։

Այնուհետև հաջորդ q տողերից յուրաքանչյուրն описվում է մեկ հարցում.

  • For range GCD queries: The line starts with the number 1 followed by two integers and (), representing the range of indices [] for which the GCD needs to be calculated.

  • For array update queries: The line starts with the number 2 followed by two integers and (), representing the index of the element to be updated and its new value .

Ելք

Յուրաքանչյուր միջակայքի GCD հարցման համար առանձին տողում տպեք տվյալ միջակայքի էլեմենտների GCD արժեքը։

Օրինակներ

Մուտք

Ելք

6 4
12 8 16 24 36 48
1 2 5
2 4 10
1 1 6
1 3 6

4
2
2

Constraints

Time limit: 0.8 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue