题目描述

尖塔我有四不玩。

战士我不玩，因为他烧，牌都烧完了我玩什么。

猎手我不玩，因为他转，转来转去像个小丑。

机器人我不玩，因为他菜。

机器人我不玩，因为他菜。

触发通晓万物了，私密马赛。

众所周知，观者打尖塔像是散步。

有一天观者在散步，她散步的区域可以看作一个圆环，分为 $n$ 个部分，每个部分有一个崎岖度 $a_i$。观者走过一段路的时间取决于她的速度与路的崎岖度，她的速度是所有她走过的路的崎岖度最大值的倒数（包括她现在在走的路），我们视她消耗的时间为崎岖度除以速度，即这段路的崎岖度乘上所有她走过的路的崎岖度最大值。

你现在要应对 $m$ 次操作：

• 操作一：观者从第 $x$ 段路走到了第 $y$ 段路，并将这些路的崎岖度加上了一个正整数 $z$（注意 $x$ 可以大于 $y$，因为区域是一个圆环）；
• 操作二：观者从第 $x$ 段路走到了第 $y$ 段路，并将这些路的崎岖度变成了正整数 $z$（同理这里 $x$ 可以大于 $y$）；
• 操作三：观者准备从第 $x$ 段路走 $t$ 个时间单位，她想知道自己最后会走到哪一个区域。

输入格式

第一行两个正整数 $n,m$，表示序列长度与操作次数。

第二行一个正整数序列，表示 $a_0,a_1,\cdots,a_{n-1}$。

接下来 $m$ 行，每行一个操作，区间加法形如 1 x y z，区间赋值形如 2 x y z，查询形如 3 x t。

请注意本题序列下标从 $0$ 开始，即 $0\leqslant x,y<n$。

输出格式

若干行每行一个非负整数，表示每次查询的答案。

4 9
1 2 3 4
3 0 4
3 0 10
3 3 11
1 1 2 3
3 0 10
3 3 11
2 1 3 2
3 0 10
3 3 11

1
2
3
1
3
3
2

样例 2~6 见下发文件：样例下载。

数据范围

对于 $100\%$ 的数据，$2\leqslant n,m\leqslant 2\times10^5,0\leqslant x,y<n,0\leqslant t\leqslant 10^{18}$，保证每个时刻每个元素都是 $[1,10^6]$ 之内的正整数。

特殊性质 A：保证没有修改

特殊性质 B：保证没有区间赋值操作。

特殊性质 C：保证操作在三种操作中均匀随机生成，每个操作的所有下标在范围内随机生成（权值除外）。