Requêtes GCD sur une plage

Vous disposez d’un tableau de n éléments ainsi que de q requêtes. Deux types de requêtes sont possibles : calculer le plus grand commun diviseur (GCD) sur une plage donnée et mettre à jour un élément à un emplacement précis. Votre objectif est de traiter ces requêtes de manière efficace.

Entrée

La première ligne de l’entrée contient deux entiers n et q (1 ≤ n, q ≤ 100 000), qui représentent respectivement le nombre d’éléments du tableau et le nombre de requêtes.

La deuxième ligne contient n entiers séparés par des espaces, (), qui correspondent aux valeurs initiales du tableau.

Les q lignes suivantes décrivent chacune une requête :

• 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 .

Sortie

Pour chaque requête de type « GCD sur une plage », affichez sur une ligne séparée la valeur du GCD des éléments dans la plage concernée.

Exemples