CF643D.Bearish Fanpages

There is a social website with n fanpages, numbered 1 through n. There are also n companies, and the i-th company owns the i-th fanpage.

Recently, the website created a feature called following. Each fanpage must choose exactly one other fanpage to follow.

The website doesn’t allow a situation where i follows j and at the same time j follows i. Also, a fanpage can't follow itself.

Let’s say that fanpage i follows some other fanpage _j_0. Also, let’s say that i is followed by k other fanpages _j_1, _j_2, ..., j__k. Then, when people visit fanpage i they see ads from k + 2 distinct companies: i, _j_0, _j_1, ..., j__k. Exactly t__i people subscribe (like) the i-th fanpage, and each of them will click exactly one add. For each of k + 1 companies _j_0, _j_1, ..., j__k, exactly people will click their ad. Remaining people will click an ad from company i (the owner of the fanpage).

The total income of the company is equal to the number of people who click ads from this copmany.

Limak and Radewoosh ask you for help. Initially, fanpage i follows fanpage f__i. Your task is to handle q queries of three types:

• 1 i j — fanpage i follows fanpage j from now. It's guaranteed that i didn't follow j just before the query. Note an extra constraint for the number of queries of this type (below, in the Input section).
• 2 i — print the total income of the i-th company.
• 3 — print two integers: the smallest income of one company and the biggest income of one company.

有一个社交网站，包含 $n$ 个粉丝专页（fanpage），编号为 $1$ 到 $n$。同时还有 $n$ 家公司，其中第 $i$ 家公司拥有第 $i$ 个粉丝专页。

最近，该网站推出了一项“关注（following）”功能。每个粉丝专页必须恰好选择一个其他粉丝专页进行关注。

网站不允许出现如下情况：粉丝专页 $i$ 关注 $j$，且同时 $j$ 也关注 $i$。此外，一个粉丝专页不能关注自己。

假设粉丝专页 $i$ 关注了另一个粉丝专页 $j_0$；又设共有 $k$ 个其他粉丝专页 $j_1, j_2, \dots, j_k$ 关注了 $i$。那么，当用户访问粉丝专页 $i$ 时，会看到来自 $k+2$ 个不同公司的广告：公司 $i$、公司 $j_0$、公司 $j_1, \dots, j_k$。恰好有 $t_i$ 人订阅（点赞）了第 $i$ 个粉丝专页，且每位订阅者将恰好点击一个广告。对于其余 $k+1$ 家公司（即 $j_0, j_1, \dots, j_k$），每家公司恰好会有 人点击其广告。剩余的 人将点击公司 $i$（即该粉丝专页所有者）的广告。

一家公司的总收入等于点击其广告的人数。

Limak 和 Radewoosh 请求你的帮助。初始时，粉丝专页 $i$ 关注粉丝专页 $f_i$。你需要处理 $q$ 个查询，共三种类型：

• 1 i j — 从现在起，粉丝专页 $i$ 改为关注粉丝专页 $j$。保证在本次查询前 $i$ 并未关注 $j$。注意：此类查询的数量有额外限制（见输入格式说明）。
• 2 i — 输出第 $i$ 家公司的总收入。
• 3 — 输出两个整数：所有公司中最小的收入值和最大的收入值。

The first line of the input contains two integers n and q (3 ≤ n ≤ 100 000, 1 ≤ q ≤ 100 000) — the number of fanpages and the number of queries, respectively.

The second line contains n integers _t_1, _t_2, ..., t__n (1 ≤ t__i ≤ 1012) where t__i denotes the number of people subscribing the i-th fanpage.

The third line contains n integers _f_1, _f_2, ..., f__n (1 ≤ f__i ≤ n). Initially, fanpage i follows fanpage f__i.

Then, q lines follow. The i-th of them describes the i-th query. The first number in the line is an integer type__i (1 ≤ type__i ≤ 3) — the type of the query.

There will be at most 50 000 queries of the first type. There will be at least one query of the second or the third type (so, the output won't be empty).

It's guaranteed that at each moment a fanpage doesn't follow itself, and that no two fanpages follow each other.

输入的第一行包含两个整数 $n$ 和 $q$（$3 \leq n \leq 100\,000$，$1 \leq q \leq 100\,000$），分别表示粉丝专页（fanpage）的数量和查询的数量。

第二行包含 $n$ 个整数 $t_1,\,t_2,\,...,\,t_n$（$1 \leq t_i \leq 10^{12}$），其中 $t_i$ 表示订阅第 $i$ 个粉丝专页的人数。

第三行包含 $n$ 个整数 $f_1,\,f_2,\,...,\,f_n$（$1 \leq f_i \leq n$）。初始时，粉丝专页 $i$ 关注粉丝专页 $f_i$。

接下来是 $q$ 行，每行描述一个查询。第 $i$ 行对应第 $i$ 个查询。该行的第一个数是一个整数 $\text{type}_i$（$1 \leq \text{type}_i \leq 3$），表示查询的类型。

第一类查询（$\text{type}_i = 1$）最多出现 $50\,000$ 次。第二类或第三类查询（$\text{type}_i = 2$ 或 $\text{type}_i = 3$）至少会出现一次（因此输出不会为空）。

保证在任意时刻，每个粉丝专页均不关注自身，且不存在两个粉丝专页相互关注的情况。

For each query of the second type print one integer in a separate line - the total income of the given company. For each query of the third type print two integers in a separate line - the minimum and the maximum total income, respectively.

对于每个第二类查询，在单独一行中输出一个整数——该公司的总收入。
对于每个第三类查询，在单独一行中输出两个整数——分别为最小总收入和最大总收入。

In the sample test, there are 5 fanpages. The i-th of them has i·10 subscribers.

On drawings, numbers of subscribers are written in circles. An arrow from A to B means that A follows B.

The left drawing shows the initial situation. The first company gets income from its own fanpage, and gets income from the 2-nd fanpage. So, the total income is 5 + 5 = 10. After the first query ("2 1") you should print 10.

The right drawing shows the situation after a query "1 4 2" (after which fanpage 4 follows fanpage 2). Then, the first company still gets income 5 from its own fanpage, but now it gets only from the 2-nd fanpage. So, the total income is 5 + 4 = 9 now.

在样例测试中，共有 5 个粉丝专页（fanpage）。其中第 $i$ 个专页拥有 $i\cdot10$ 位订阅者。

图中圆圈内标出的是各专页的订阅者数量。从 $A$ 指向 $B$ 的箭头表示 $A$ 关注了 $B$。

左侧图示表示初始状态。第一家公司的收入来源包括：其自身专页带来的收入 ，以及来自第 2 个专页的收入 。因此，总收入为 $5 + 5 = 10$。执行第一个查询（"2 1"）后，应输出 10。

右侧图示表示执行查询 "1 4 2"（即让专页 4 关注专页 2）之后的状态。此时，第一家公司的自身专页收入仍为 5，但来自第 2 个专页的收入变为 。因此，当前总收入为 $5 + 4 = 9$。