Problem: Yuezheng Ling gives Luo Tianyi a tree which has n nodes, rooted at 1. 

Luo Tianyi will tell you that the parent of the i-th node is a_i (1 ≤ a_i<i for 2 ≤ i ≤ n), and she will ask you to perform q queries of 2 types:

  1. She'll give you three integers l, r and x (2 ≤ l ≤ r ≤ n, 1 ≤ x ≤ 10^5). You need to replace a_i with max(a_i-x,1) for all i with l ≤ i ≤ r.
  2. She'll give you two integers u, v (1 ≤ u, v ≤ n). You need to find the [LCA](https://en.wikipedia.org/wiki/Lowest_common_ancestor) of nodes u and v (their lowest common ancestor).

Input

The first line contains two integers n and q (2≤ n,q ≤ 10^5) — the number of nodes and the number of queries, respectively.

The second line contains n-1 integers a_2, a_3,..., a_n (1 ≤ a_i < i), where a_i is the parent of the node i.

Next q lines contain queries. For each query, the first integer of each line is t (t = 1 or 2) — the type of the query. 

If t = 1, this represents the query of the first type. Then, three integers will follow: l, r, x (2 ≤ l ≤ r ≤ n, 1 ≤ x ≤ 10^5), meaning that you have to replace a_i with max(a_i-x,1) for all i with l ≤ i ≤ r.

If t = 2, this represents the query of the second type. Then, two integers will follow: u and v (1 ≤ u, v ≤ n), and you have to find the LCA of u and v. 

It's guaranteed that there is at least one query of the second type.

Output

For each query of the second type output answer on a new line.

Example

Input


6 4
1 2 3 3 4
2 3 4
1 2 3 1
2 5 6
2 2 3


Output


3
3
1

Note

The tree in example is shown below.

<image>

After the query of the first type, the tree changes and is looking as shown below.

<image>

Solution (in CPP):

Solution:
/*
; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 
; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i i i i i i i i i i ; D i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 
; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i i i i ; ; ; i i i i i i i i i i i i D D i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 
; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i i i i i i i i i i i i i i i i i i D D i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 
; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i ; ; i i i i i i i i i i i i i i i i i i i i D D i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 
; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i i i i i i i i i i i i i i i i i i i i i f D D i i i i i i i i i i i i i i i i i i i i i i i i i i i i 
; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i i i i i i i i i i i i G i i i i i i i i i D D E i i i i i i i i i i i i i i i i i i i i i i i i i i i 
; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i ; ; ; i i i i i i i i i i i E i i i i i i i i i D D D i i i i i i i i i i i i i i i i i i i i i i i i i i i 
; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i i i i i i i i i i i t D i i i i i i i i D D D D i i i i i i i i i i i i i i i i i i i i i i i i i i i 
; ; ; ; ; ; ; ; ; ; ; ; ; i i ; ; ; i i i i i i i i i i i i i K i i i i i i i D D D D i i i i i i i i i i i i i i i i i i i i i i i i i i i 
; ; ; ; ; ; ; ; ; ; ; ; ; i i i i i i i i i i i i i i i i i i i G i i i i i i D D D i i i i i i i i i i i i i i i i i i i i i i i i i i i i 
; ; ; ; ; ; ; ; ; ; ; ; i D , i i i i i i i i i i i i i i i i i D E i i i i i D D i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 
; ; ; ; ; ; ; ; ; ; ; i i i D D D D G : ; i i i i ; ; i i i i i D E i i i i i D E i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 
; ; ; ; ; ; ; ; ; ; i ; ; ; ; i D D D D D D G D D D D D D D i i , E ; i i i i G i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 
; ; ; ; ; ; ; ; ; ; ; ; ; i ; ; i i D D E E E D D D D D D D G i D K D i i i i G f i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 
; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i i i i ; D D E D D D G G L G G E D E D G G D K i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 
; ; ; ; ; ; ; ; ; ; ; ; ; i ; i i ; ; ; i i i L E j i i i i i E D D E D G D D D D i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 
; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i i i i i i i E D G D E G D K E E D D G G D D D D i i i i i i i i i i i i i i i i i i i i i i i i i i i t 
; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i i i i i i i i i i i E E E E E E D E D G G G D D D D i i i i i i i i i i i i i i i i i i i i i i i i i i i t 
; ; ; ; ; ; ; i i i i i i i i i i i i i i i i i i i i i ; W W K D E D G G G D E D D G i i i i i i i i i i i i i i i i i i i i i i i i t t i 
; ; i ; ; ; i ; i i i i i i i i i i i i i i i i i i i ; i K E E D D D G G D D D D D D i i i i i i i i i i i i i i i i i i i i i i i i i t t 
; ; ; ; ; ; ; i i i i i i i i i i i i i i i i i i i i i D W D D D D D D D D D E D D D D i i i i i i i i i i i i i i i i i i i i i i t t t t 
; ; i i i i i i i i i i i i i i i i i i i i i i i i i j D E D D D D D D D D D D D D D L i i i i i i i i i i i i i i i i i i i t t t t t t t 
; i i i i i i i i i i i i i i i i i i i i i i i i i f D D G D D D D G D D D E D D D D D D i i i i i i i i i i i i i i i i t t t t t t t t t 
i ; ; i i i i i i i i i i i i i i i i i i i i i i ; f D D D D D D D G D D D G G G D L E i i i i i i i i i i i i i i i t i t t t t t t t t t 
i i i i i i i i i i i i i i i i i i i i i i i i i j i j E D D D D G D D E E G K D D D E D i i i i i i i i i i i i i t t t t t t t t t t t t 
i i i i i i i i i i i i i i i i i i i i i i i i i , ; ; G D D E E W K G G G G G G f E D i i i i i i i i i i i i t t t t t t t t t t t t t t 
i i i i i i i i i i i i i i i i i i i i i i i i i , i , i G D D D G D G G G G G G D D i i i i i i i i i i i i i t t t t t t t t t t t t t t 
i i i i i i i i i i i i i i i i i i i i i i i i i i i i i D D D D G G G G G G G G D j D E L i i i i i i i t t t t t t t t t t t t t t t t t 
i i i i i i i i i i i i i i i i i i i i i i i i i i i i D f G G D G G G G G D D D E D j i D E i i t t t t t t t t t t t t t t t t t t t t t 
i i i i i i i i i i i i i i i i i i i i i i i i D i i , j j t ; D i D G G G G D D D D i i i i t t t t t t t t t t t t t t t t t t t i i i i 
i i i i i i i i i i i i i i i i i i i i i i i i L i i t t , i i i i G D D G L j E E D E i t t t t t t t t t t t t t t t t t t t t t i i i i 
i i i i i i i i i i i i i i i i i i i i i i i i i i L , i i i i i t # D D E W j E t G i i t t i t t t t t t t t t t t t t t t t t t t i i i 
i i i i i i i i i i i i i i i i i i i i i i i i i i t i i i i i i t W D E E W D G G D D t t t t t t t t t t t t t t t t t t t t t t t i i i 
i i i i i i i i i i i i i i i i i i i K i i i i i i i i . G G G G G W W W W W K G G G G t t t t t t t t t t t t t t t t t t t i i i i i i i 
i i i i i i i i i i i i i i i i i i i i i i i i i i i i G G G G G G W # W W # W W G G G i t t t t t t t t t t t t t t t i i i i t t i i i i 
i i i i D i i i i i i i i i i i i i i i i i i i i i i i G G G G G G W W W W W W W W G G D t t t t t t t t t t t t t t t i i t t j t i i i i 
i i i i D t i i i i i i i i t i i i i i i i i i i i i i G G G G D E K D D W W K G D D G t t t t t t t t t t t t t t t t i i i t j t t t t i 
i i i i i i i i i i i i i t i i i i t i i i i i i i t t G K K G K D D # D G G G D E G t t j t t t t t t t t t t t t t t t t i t t t j j j j 
i i i i i i i i i i i i i i i i i i i i i i i i t i t t K W K W K K # E # G G W E G G t t t t t t t t t t t t t t t j j t t t t t t t j j j 
i i i i i i i i i i i i i i i i i i i i i i i i t t t t K K K W K D D W G G G G G K K K K t t t t t t t t t t t t t t j t j t t t t t j j j 
i i i i i i i i i i i i i i i i i i i i i i i t i t t t K W G K D W W L G G W G G G K G G t t t t t t t t t t t t t t t t j t j t t t j i f 
i i i i i i i i i i i i i i L D i i i i i i i i i i t t K K K K G W L L G G W D G W G G G t t t t t t t i # E D t t t t t t t t t t t t t t 
i i i i i i i i i i i i i i t i i i i i i i i i i i i i G D D D G L L G G # G D K K K D G L t t t t t t W K W D t t t t t t t t t t t t t t 
i i i i i i i i i i i i i i i t i i i t i i i i i i L G G G G G G L G G G W D K K K K D D i t t t t t W # W # t t t t t t t t t t t t t t t 
t t i i i t i i t t t t i i i t j t j j t t t i t j j j j G G K L G G G K D W # W W W D D t i i t t # W W W t t t t t t t t t t t t t t t i 
j t t t t t t i t t j j t t i t j j j j j t t f f f f f D G K G G G G G W W W W W W W D i i i t i L W W W t t t t t t t t t t t t t t t t t 
j t t t t t i i t t j t t t t j j j j t i t j t t j L D D D W G G G G D W W W K D D W D i i i i ; W W W i t t i i t t t t t t t t t t t t t 
j j j j t t t t t t t j j j j j j j t j t L f G D D D D D K W G D D K D W W W W G D W K ; i i t W W W i i i t i t t t t t t t t t t t t t t 
j j j j f j j t t t t j j j j t j t t j f G D D D D D D D W W E D K W W W W K W D D W K i t G W W W i i t t t t t t t t t t t t t t t t t t 
j j j j f f j j j j j t t t t t j t j G G D D D E E E D K W W W K W W W W W K W W W W K t t # E D i i t t t t t t t t t t t t t t t t t t t 
t j t j j j j j j j j j t t t t j j E G G G D E E E E K W W K K W W W W W W W K W W W K K D W E t t t t t t t t t t t t t t t t t t t t t t 
t t t t j j j j j j j j j t t t j E E E E E E E E E E W W K K K K W W W E D G E D K D K # W W t t j j j j t j j t j t t t j j t t t t j j t 
t t E j t j j j t t j j j j t t G G G G G G G D D D W W K K W W K W W E W W D E E W E W W W j f j j f f j t t f t D G j j t j t j t j j j j 
j E E D D K K K t t j t f f f G L E G G G G G E E W K K W K K K W W W W W E E D D W K W W f f f # ; f j j D K K W E G E f f j j j j j j j j 
E E E D D E E E E K K K E f j j t j G E G G D G W K K W W W K K W W W W D E D E E D W K W f f D K # E G W E K D W W E E j j j j j j f f j f 
E E E E G E E E E E E E E E K K W W E L L G G W K j j W E K W W W W W W W E E E E D D L j f D D W E E D G D j f f f f f j j j f f f f f j j 
E E E E E E E E E E E E E E E E E G K K W K K K j W W K K K K W W W W D K W W D D G G G D W K W # # D f f f f f j f f f j j f f f j j j j t 
f f j j j j f D E E E E G D E G G G G G G G D j W W W W W K K W W W W E W K W G D D D G D W W K # # j f f f f f f f f f f f f f f j j j j j 
f f f j j f f f f f j G G G D j j f f f f j j j K D K K W W W W W W W W K W D G D D G D W f f G j j f f f f f f f f f f f j f G f j j j j f 
f f f f f f f f f j f j j j j j j j j j f f j W W K K K W W W W W W K W K W K K G D G G D j j j j f L D f f j f f f f f f f j t L f f f f f 
f f f f f f f f f f f L j t f j f f f f f f f W K K K K K W W W W W W W W W K W W G G G G j t j f f L G E f f f f f f f f f f f t j f f f f 
f f f j f f f f f f f f L L j j f j f j f j W W W W K K W W W W W W W W E # W K W W G G G j j j f f f f j G f f j f f f f f f f f f f t f f 
E f f f f t j L f f f j t j f j f i f f j W W K i D W K W W W W W W W W K W G G W W W K G G j j f f f f j j G j L f G j f f f L f f f f f f 
D E f f f f j f G f j f j f j L f f f L j W K K , D D W W W W W W K W D W K G G G W W W D K j j f f j f j f j D j j f L G G f j G L f f f f 
G G L f f f f f f f L j j L f G D j j f j W W E i D D D W W W W W W W K K W D G G G G W K K E j j t f f j f L L j j j G L G E f f L G f f f 
f f f f f f f t f f f L f j f L L L j j f L W j t D D D D # W W W W W W W W E L E D G G G D K j f j j j f G f j G G j j G G f D L t L G f j 
f f f L f f f f f f f L G f L j f f f j f j j f f D D D W W W W W W W W W W # G G D E G G G G f f f L j j L G G G G E D f L D f G D L f G f 
f f L j G f L j f f f f f f f f f t D L f f f f G D D D W W D W W K K K W W W E G G D E G G G t f j f f j f G D L j G j E f f j f G D f L G 
f f f f f f G L j f f f f L f f f f f D G t f G G D D K W D D D W W W W W D W D G G G E E G G G L f f f f f L G G j f D f D L L f f L D f f 
G f f f f G f G j j G f f f f L f f j L L G f f G D K K W D D D D W W W W D W W D G G G E E E G f G j j f ; f j G G f f D t D f L f f f G t 
f L f f f G G f f j L L D G f L f f f j f L f f D K K E G G D D D D W f f D W W W G G G G G E E f D G G j j f f f G L f f f f D G f G f f f 
f f L f f j G G D f t f L G E L j f j f f f f L K E E G G G G D D D D f : D W W W D D D G G G W E G D G G j f f f L G L j L f f j L f f L f 
f f f f f f f f f G D t f f f G G f L f L f W W K K G L G D D G D D E f f D D W W W D G G G W W L G L G G D G f f f f f j G D f f L L f G L 
f f L f L f f j f j G D j f D f G j # W W W D D D D L G G G D G D D E G f G D W D D D D D W W E D G f f D G G D L L L L f L G f L j G f L G 
f j f f L j j f L f G G D f L j W K E D D D D D E D G G G f D G G D K f G G D G D W D W W W D D G D G f f f L G L E f L L L L E f f f f j j 
f f j f j L f f f f L G D G f W W K D E D D E K f D G G G G G D G D G D L t D D K E W # D D D D L G D G L f L G f L E G f L f f G f f D G L 
L f j f j L f j j L j i G D W W W D D D D D K L f D G G G G G G D G L i D L G D E G G D G G G D G G L G E L f G L j D f G L L f E L G f f f 
j f L L L j D G G f L f W E W E D D D D D K f L L D D G G G G G G G G G G D L D D G G L D D G G f L G L G L L f G L G j E f L L L j G f L f 
G L L G D G L f L G K # W W E D D G G G W D L E f D D G G G G G G E L G f L L D D G f G G G D D D L j G G G f f f f D j f E L f f G j G j f 
f L G L D G G f L D D E G L G f f L L W G f L L D D D G G G G G G G G L f j j f D D G G D G D G D L f E G f D f f G D D L f D f f E f L L f 
f f L L G G K E E i ; E D t f L j L f j G G D E f D D G G G G G G G D j f j f L D D G G G G G D D E G f f G f j f f G D G E f G L f f f G G 
L f f L G G G G L f E K K j f D j f L f j f L G E f D G G G G G G G f f G f L G L D D G G G G G G t D f G f G E L j f L G L D G L f f f f L 
j f f f f L G f D j f G G E f L G f L f f j f L L L D G G G G G G G L f f f f f L E D G G G G G G E f E f L L j G f f f L G L D L G K f f f 
f L f f f f f G f f f j L G f f D f f L f G f j L D D G G G G G G G j f f L f f L f D G G G G G G G f j G j L f E G f f f L G L G D G f f j 
*/

#include <cmath>
#include <stdio.h>
#define LL long long
using namespace std;
const int Rea=1e5+3;
struct Rin
{
    char c;
    inline char gc()
    {
        static char rea[Rea];
        static char *head,*tail;
        return head==tail&&(tail=(head=rea)+fread(rea,1,Rea,stdin),head==tail)?EOF:*head++;
    }
    inline Rin&operator >>(int &x)
    {
        x=0;
        bool tag=false;
        for(c=gc();c>'9'||c<'0';c=gc())if(c=='-'){c=gc();tag=true;break;}
        for(;c>='0'&&c<='9';c=gc())x=(x<<1)+(x<<3)+(c^'0');
        if(tag)x=-x;
        return *this;
    }
}rin;
inline void jh(int &x,int &y){if(x^y)x^=y^=x^=y;return;}
inline int min(int x,int y){return x<y?x:y;}
inline int max(int x,int y){return x>y?x:y;}

const int K=323;
const int N=1e5+K;
int n,m,L,ks;
int a[N];
int f[N];
int del[K];
bool tag[K];
int lasten;
inline int bel(int x){if(x==1)return 0;return (x-2)/L+1;}
inline int step(int x){return tag[bel(x)]?max(1,a[x]-del[bel(x)]):f[x];}
inline void build(int l,int r,int num){tag[num]=true;for(int i=l;i<=r;i++)f[i]=(a[i]<l)?(a[i]):(tag[num]=false,f[a[i]]);return;}
inline void init(){L=sqrt(n-1);ks=(n-1)/L;if((n-1)%L)ks++;for(int l=2,r,i=1;r=min(l+L-1,n),l<=n;l=r+1,i++)build(l,r,i);return;}
inline void Gura(int &x){x^=lasten;return;}
inline void Ame(int l,int r,int num,int x)
{
    if(!tag[num]){for(int i=l;i<=r;i++)a[i]=max(a[i]-x,1);build((num-1)*L+2,num*L+1,num);}
    else for(int i=l;i<=r;i++)f[i]=a[i]=max(a[i]-x,1);return;
}
inline void work()
{
    int typ,l,r,x;rin>>typ;
    if(typ==1)
    {
        rin>>l>>r>>x;l=max(l,2);if(l>r)return;
        int ls=bel(l),rs=bel(r);
        if(ls==rs){Ame(l,r,ls,x);return;}
        Ame(l,ls*L+1,ls,x);Ame((rs-1)*L+2,r,rs,x);
        for(int i=ls+1;i<rs;i++)if(tag[i]){del[i]+=x;if(del[i]>=(n<<1))del[i]-=n;}else Ame((i-1)*L+2,i*L+1,i,x);
    }
    else
    {
        rin>>l>>r;if(l>r)jh(l,r);
        for(;step(r)!=step(l);){r=step(r);if(bel(l)>bel(r))jh(l,r);}
        if(l>r)jh(l,r);for(;r!=l;r=max(1,a[r]-del[bel(r)]))if(l>r)jh(l,r);
        printf("%d\n",lasten=l);
    }
    
    return;
}
int main()
{
    rin>>n>>m;a[1]=f[1]=1;for(int i=2;i<=n;i++)rin>>a[i];init();for(;m;m--)work();
    return 0;
}