解题思路

给定长度为 n 的数组 a，定义三元组 (i,j,k)（i<j<k）为“好”的充要条件是 三对数的 gcd 要么全部为 1，要么全部大于 1。

关键观察：Ramsey 定理给出 R(3,3)=6——任意 6 个点的完全图二染色（两种颜色分别代表“gcd=1 的边”和“gcd>1 的边”）中，必然存在一个单色三角形。 对应到本题，当 n ≥ 6 时，不管数组取值如何，前 6 个下标中一定存在一个好三元组（三对 gcd 全为 1 或全大于 1）。

据此可将问题大幅简化为常数规模检查：

题目内容

给定一个长度为 $n$ 的数组 $a$ 。一个整数三元组 $(i,j,k)$ 被称为好的当且仅当：

$1≤i<j<k≤n$ ；

其三个元素对应的 $gcd$ 值要么全部为 $1$ ，要么全部大于 $1$ ，使用数学语言表达，即 $max${$gcd(a_i,a_j),gcd(a_j,a_k),gcd(a_i,a_k)$}$=1$ 或 $min$ {$gcd(a_i,a_j),gcd(a_j,a_k),gcd(a_i,a_k)>1$ 。

小美有 $q$ 次对数组 $a$ 的更新。每次更新会给你两个整数 $p$ 和 $x$，代表将 $a_p$ 赋值为 $x$ 。在每一次更新之后，你需要告诉小美是否存在好三元组。如果存在请输出任意一个。

输入描述

第一行输入两个整数 $n,q(3≦n≦2·10^5,1≦q≦2·10^5)$ ，分别表示数组 $a$ 的长度和更新的次数。

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1 ≦ a_i≦ 10^6)$ ，表示初始数组 $a$ 中的元素。

接下来 $q$ 行，第 $i$ 行输入两个整数 $p_i,x_i(1≦p_i≦n,1≦x_i≦10^6)$ ，表示将 $a_{p_i}$ 赋值为 $x_i$ 。

输出描述

对于每次更新，如果在更新后不存在好三元组，则输出一行 $NO$ 。

否则，在第一行输出 $YES$ 。第二行输出三个整数 $(i,j,k)$ ，代表你找到的好三元组。

您可以以任何大小写形式输出答案。例如，字符串 $yEs、yes$ 和 $Yes$ 都将被视为肯定的回答。

样例1

输入

4 3
2 2 3 10
4 3
1 1
1 6

输出

NO
YES
1 2 3
YES
1 3 4

说明

初始数组 $a =${$2,2,3,10$} 。

第一次更新后，$a$ 变为 {$2,2,3,3$}，可以证明不存在好三元组。

第二次更新后，$a$ 变为 {$1,2,3,3$}。$(1,2,3)$ 为一个好三元组，因为 $max(gcd(a_1,a_2),gcd(a_2,a_3),gcd(a_1,a_3))=max(1,1,1)=1$ 。

第三次更新后，$a$ 变为 {$6,2,3,3$}。$(1,3,4)$ 为一个好三元组，因为 $min(gcd(a_1,a_3),gcd(a_3,a_4),gcd(a_1,a_4))= min(3, 3, 3)= 3$ 。