记者们喜欢聚在一起搞大新闻。

HK一共有 \(N\) 位记者。每位记者都有他仰慕的人，且没有两位记者互相仰慕。每位记者不总是仰慕同一个人。

每位记者都有一定的新闻素材，第 \(i\) 位记者有 \(c_i\) 份素材。

现在记者们想交换素材。每位记者都会把自己拥有的一部分素材送给他仰慕的人和仰慕他的人，具体来说，假设一位记者有 \(c\) 份素材，要送给 \(k\) 个人，则他要给每个人送 $ \lfloor\frac c{k+1}\rfloor $份 素材，剩下的自己保有。 注意，自己将会失去送出去的素材。 记者们想知道，交换素材后，自己的素材的数量，以及素材最少/多的人的素材数量。

第一行两个正整数 \(N,Q\) ，分别表示记者数和发生的事件数。

第二行 \(N\) 个正整数 \(c_1,c_2,\dots,c_N\) 。

第三行 \(N\) 个正整数 \(a_1,a_2,\dots,a_i\) ，表示每位记者仰慕的人。

接下来 \(Q\) 行，有三种事件：

• 1 x y，表示记者 \(x\) 仰慕的人变成了 \(y\) 。
• 2 x，询问如果记者们交换了素材，第 \(x\) 位记者最终的素材数量。
• 3，询问如果记者们交换了素材，素材最少/多的人最终的素材数量。

对于第2种事件，输出一个整数，表示交换后第 \(x\) 位记者的素材数量。

对于第3种事件，输出两个整数，依次表示交换后素材最少/多的人最终的素材数量。

样例解释

修改前每位记者仰慕的人以及交换后每位记者的素材数量：

修改后每位记者仰慕的人以及交换后每位记者的素材数量：

样例输入、输出2

见下发文件news.in/out。

数据规模与约定

对于 \(30\%\) 的数据，有 \(3\le N\le 5000,1\le Q\le 5000\)。

对于 \(50\%\) 的数据，有 \(3\le N\le 30000,1\le Q\le 30000\)。

对于 \(100\%\) 的数据，有 \(3\le N\le 100000,1\le Q\le 100000,1\le c_i\le 10^{12},1\le a_i,x,y\le N,a_{a_i}\neq i\) ，保证事件1的发生次数不超过 \(50000\) 。