You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

$ljd$给了你一个包含$n$个不同正整数的$set$容器，他想知道这些数的最大公约数是什么，你运用刚学的数论知识解决了这个问题，很快就告诉了$ljd$答案，但$ljd$觉得这太简单了，于是他对容器进行了$q$次增删元素的操作，问每次操作后$set$容器内所有数的最大公约数是什么，你还能解决这个问题吗？

Format

Input

第一行有两个正整数 $n, q$( $1 \le n, q \le 2e5$ )。其中 $n$ 代表 $set$ 初始大小， $q$ 代表操作次数

第二行有 $n$ 个正整数, $a_1,a_2, \dots ,a_n$( $1 \le a_i \le 2e5$ ), 代表 $set$ 初始元素。

接下来 $q$ ($1 \le q \le 2e5$) 行，每行有两个整数，$opt$ 和 $x$:

• $opt$为$1$时向容器插入正整数$x$
• $opt$为$2$时从容器删去正整数$x$

测试数据保证$set$中的数不会重复。$set$永不为空，并且不会插入已有的数，也不会删去没有的数

Output

对于每次操作，输出当前$set$中所有数的最大公约数

Samples

4 5
4 8 12 16
1 32
2 4
2 12
2 8
1 5

4
4
8
16
1