蛤蟆 $\texttt{\color{red}z\color{black}yc}$ 由于在 IOCS2024 第一试中被加 QQ 买洞洞鞋而赚的盆满钵满，因而转头开始研究他的老本行：修线。

蛤蟆 $\texttt{\color{red}z\color{black}yc}$ 眼前有一个序列 $a$，其中有若干个位置是要被修的，这些位置的 $a_i=-1$。$\texttt{\color{red}z\color{black}yc}$ 需要将每个要修的位置填上一个 $\in[0,10^{12}]$ 的数。

在之后的时刻中有 $q$ 个顾客到来，顾客会给出一个区间 $[l,r]$，$\texttt{\color{red}z\color{black}yc}$ 需要在修好 $a$ 之后从 $a_l\sim a_r$ 中选取一个子区间 $[l',r']$ 满足 $[l',r']$ 的每一个前缀和均为完全平方数，再将子区间的最大长度给顾客。

$\texttt{\color{red}z\color{black}yc}$ 具有超时空性质，所以在上一个顾客走后 $a$ 将会恢复原样。但是有些顾客还可能会搞破坏，即将 $a$ 中的某个数变成另一个数，此时 $a$ 将不会恢复原样。

由于蛤蟆 $\texttt{\color{red}z\color{black}yc}$ 还在卖他的洞洞鞋，无暇顾及修线，于是修线的任务就交给聪明的选手了！

题目描述

给定一个长度为 $n$ 的序列 $a$，其中 $a_i \in [-1,10^6]$。

我们称 $a$ 序列的一个区间 $[l,r]$ 是好的，当且仅当：

• 存在一种将 $a_{l},a_{l+1},\dots,a_{r}$ 中值为 $-1$ 的元素分别替换成 $[0,10^{12}]$ 内的整数的方案，使得 $\forall k \in [l,r],\sum_{i=l}^{k}a_i$ 为完全平方数。（特殊地，我们规定 $0$ 也是完全平方数）

现在有 $q$ 次操作，每次操作为以下两种之一：

• 1 i x：将 $a_i$ 替换为 $x$。

• 2 l r：询问区间 $[l,r]$ 内的最长合法子区间的长度。特殊地，如果不存在请输出 $0$。

输入格式

第一行两个整数，分别代表 $n,q$。

第二行一行 $n$ 个整数，其中第 $i$ 个数表示 $a_i$。

接下来 $q$ 行，每行有三个整数，表示一次操作。其格式在上文已给出。

输出格式

对于每个第二类操作，输出一行一个整数表示答案。

样例 #1

样例输入 #1

5 7
-1 -1 -1 -1 -1
2 2 4
2 1 5
1 3 16
1 2 9
2 1 3
2 2 5
2 1 5

样例输出 #1

3
5
3
4
5

提示

数据范围

对于 $100\%$ 的数据满足：$1 \leq n,q \leq 66666$，$a_i \in [-1,10^6]$。

• 特殊性质 A：保证询问区间非 $-1$ 元素个数不超过 $16$ 个。

• 特殊性质 B：保证任意时刻序列中均不存在 $-1$。