题目内容

给定一个长度为 $n$ 的正整数序列 $a_1, a_2, \dots, a_n$。 定义两个元素的「亲和值」为它们的最大公约数，即 $\gcd(a_i, a_j)$。 一个三元组 $(i, j, k)$（$1 \le i < j < k \le n$）被称为和谐的，当且仅当三个亲和值 $\gcd(a_i, a_j), \gcd(a_j, a_k), \gcd(a_i, a_k)$ 要么全部等于 $1$，要么全部大于 $1$。

现在将对该序列依次进行 $q$ 次修改操作。每次修改会给出位置 $p$ 和新值 $x$，表示将 $a_p$ 变为 $x$。请在每次修改后判断序列中是否存在和谐三元组，若存在则需要输出任意一个。

数据范围：

• 序列长度 $n$ 满足 $3 \le n \le 2 imes 10^5$。
• 修改次数 $q$ 满足 $1 \le q \le 2 imes 10^5$。