给定一棵N个节点的树，编号1~N。其中1号节点是根，并且第i个节点的权值是V_i。

针对这棵树，小Hi会询问小Ho一系列问题。每次小Hi会指定一个节点x，询问小Ho以x为根的子树中，最小的权值是多少。为了增加难度，小Hi可能随时改变其中每个节点的权值。

你能帮助小Ho准确、快速的回答小Hi的问题吗？

Input

第一行一个正整数N。

第二行N个整数，V₁, V₂, ... V_N。

第三行n-1个正整数，第i个数P_i表示第i+1号节点的父结点是第P_i号节点。注意1号节点是根。

第四行一个正整数Q，表示有Q个询问/修改权值。

接下来Q行，每行可能有如下两种输入格式：

1 x u

2 x

第一种表示将第x号节点的权值修改为u

第二种表示询问以第x号节点为根的子树中，最小的权值是多少。

对于30%的数据，1 ≤ N, Q ≤ 1000

对于100%的数据，1 ≤ N, Q ≤ 100000, -10⁹ <= V_i, u <= 10⁹

Output

对于每次询问，输出一个整数表示答案。

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int maxn=;

int sa[maxn],Rank[maxn];

int Laxt[maxn],Next[maxn],To[maxn],cnt;

int fa[maxn],a[maxn],sz[maxn],tot=;

int ch[maxn][],Min[maxn];

void add(int u,int v)

{

    Next[++cnt]=Laxt[u];

    Laxt[u]=cnt;

    To[cnt]=v;

}

int dfs(int u)

{

    sz[u]=;

    for(int i=Laxt[u];i;i=Next[i]){

        int v=To[i];

        sa[v]=++tot;

        Rank[tot]=v;

        sz[u]+=dfs(v);

    } return sz[u];

}

void update(int Now)

{

    Min[Now]=min(Min[Now<<],Min[Now<<|]);

}

void build(int Now,int L,int R)

{

    if(L==R) { Min[Now]=a[Rank[L]]; return ;}

    int Mid=(L+R)>>;

    build(Now<<,L,Mid);

    build(Now<<|,Mid+,R);

    update(Now);

}

int query(int Now,int L,int R,int l,int r)

{

    if(l<=L&&r>=R) return Min[Now];

    int Mid=(L+R)>>;

    if(r<=Mid) return query(Now<<,L,Mid,l,r);

    else if(l>Mid) return query(Now<<|,Mid+,R,l,r);

    else return min(query(Now<<,L,Mid,l,Mid),query(Now<<|,Mid+,R,Mid+,r));

}

void change(int Now,int L,int R,int x,int val)

{

    if(L==R) { Min[Now]=val;return ;}

    int Mid=(L+R)>>;

    if(x<=Mid) change(Now<<,L,Mid,x,val);

    else change(Now<<|,Mid+,R,x,val);

    update(Now);

}

int main()

{

     int i,j,n,q,x,y,opt;

     scanf("%d",&n);

     for(i=;i<=n;i++) scanf("%d",&a[i]);

     for(i=;i<=n;i++) scanf("%d",&fa[i]),add(fa[i],i);

     sa[]=; Rank[]=; dfs(); build(,,n);

     scanf("%d",&q);

     for(i=;i<=q;i++){

         scanf("%d",&opt);

         if(opt==) scanf("%d%d",&x,&y),change(,,n,sa[x],y);

         else {

            scanf("%d",&x);

            printf("%d\n",query(,,n,sa[x],sa[x]+sz[x]-));

        }

     }

     return ;

}