점수 관리자

경비원, 촬영: Collin Armstrong, Unsplash

당신은 친구들과 게임을 하는 것을 매우 좋아한다. 하지만 이번에는 당신이 점수 관리자를 맡을 차례이므로 상황이 다르다. 친구들은 보드 위에 $1$부터 $n$까지 번호가 매겨진 $n$개의 칸이 있고, 각 칸에 어떤 수가 들어 있는 게임을 하고 있다.

각 라운드에서 플레이어는 다음 두 행동 중 하나를 할 수 있다.

• 어떤 칸 하나를 선택하고 그 칸에 있는 수를 바꾼다.

• $1 \leq j \leq k \leq n$를 만족하는 두 수 $j$와 $k$를 선택하고,

점을 얻는다. 여기서 $a_i$는 $i$번째 칸에 있는 수이며, $p\oplus q = \mathrm{gcd}(p,q)$는 $p$와 $q$의 최대공약수, 즉 $p/s$와 $q/s$가 모두 나머지 없는 정수가 되게 하는 가장 큰 정수 $s$를 나타낸다.

당신은 게임의 목표가 무엇인지 정확히 알지 못하지만, 그것은 전혀 중요하지 않다. 당신이 해야 할 일은 점수를 기록하는 것뿐이다.

점수 배점

그룹 | 점수 | 제한

1 | 50 | $1 \leq n, q \leq 100$

2 | 50 | 추가 제한 없음

첫째 줄에는 칸의 수와 라운드의 수를 나타내는 두 정수 $n$와 $q$ ($1 \leq n, q \leq 10^5$)가 주어진다. 둘째 줄에는 $n$개의 정수 $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$)가 주어지며, $a_i$는 번호가 $i$인 칸에 처음 들어 있는 수이다. 다음 $q$개의 줄은 라운드를 나타내며, 각 줄에는 세 수 $x$, $y$, $z$가 주어진다. $x=1$이면 플레이어는 번호가 $y$인 칸의 수를 $z$로 바꾸었다 ($1 \leq y \leq n$, $1 \leq z \leq 10^9$). 반면 $x=2$이면 플레이어는 $j=y$와 $k=z$을 사용해 두 번째 행동을 수행했으며 ($1\leq y \leq z \leq n$), 그에 따라 점수를 얻는다.

플레이어가 두 번째 행동을 수행한 각 라운드에 대해, 그 라운드에서 플레이어가 얻은 점수를 한 줄에 출력한다.