Sunny is the commander of a Clay Battalion which consists of $N$ clay troopers, numbered from $1$ to $N$.
Trooper $i$ has an initial of battle power $A_i$ ($1\le i\le N$).

Sunny has decided to implement the TFT — Trooper Flexibility Training, to increase the overall battle strength of his battalion.
As Sunny is a busy man, he has decided to create a hierarchy within the battalion, in which trooper $P_i$ ($P_i \lt i$) trains trooper $i$, except for trooper $1$ who is only trained by Sunny himself, therefore $P_1 = 0$.

When trooper $i$ is trained, it trains all troopers $j$ whose $P_j=i$ with the same training it was trained with.
Note that the hierarchy is designed in such a way where by training trooper $1$, the entire battalion will be trained.

Sunny would like to peform some different trainings and queries to boost the battalion's battle strength.

1. Sunny trains trooper $i$, which increases $A_i$ by $v$.
2. Sunny trains trooper $i$, which $A_i=max(A_i, v)$.
3. Sunny would like to target his trainings at specific troopers. Hence, he is going to ask you about trooper $i$.
   Formally, Sunny would like to know the minimum battle power among all troopers that trooper $i$ directly or indirectly trains including trooper $i$.

Please answer all of Sunny's queries to help him complete his TFT — Trooper Flexibility Training.

Input

The first line of input contains two integers, $N$ and $Q$ — the number of clay troopers within Sunny's battalion and the total number of trainings and queries.
The second line of input contains $[A_1, A_2, \dots, A_N]$ — the initial battle power of trooper $i$.
The third line of input contains $[P_1, P_2, \dots, P_N]$ — describing the training hierarchy within the battalion.
The next $Q$ lines contains the parameters to a training or query.
The first two integers on the line, $T_i$ and $u$ are the type of the operation and the number of the trooper which the operation specifies.
($1\le T_i \le 3$, $1\le u\le N$).
If $T_i=1$ or $2$, an integer $v$ follows. ($1\le v\le 10^9$).

Output

For each query of type 3, output an integer on a line — the answer to the query.

Constraints

For all subtasks, $1\le N, Q\le 3\times 10^5$, $1\le A_i, v\le 10^9$, $0\le P_i \le N-1, 1\le u\le N$
Subtask 1 (10%): $T_i=3$
Subtask 2 (20%): $1\le N, Q\le 1000$
Subtask 3 (40%): There is only one kind of training
Subtask 4 (30%): No additional constraints