题目描述
给序列 a1,…,an 和排列 b1,…,bn,共有 m 次操作:
修改操作:给定 x,y,将 ax 改为 y;
查询操作:给定 l,r,x,查区间 [l,r] 内最长的子区间 [l′,r′](即满足 l≤l′≤r′≤r),使得对 l′≤i<r 有 ai+1=bai,且存在 l′≤i≤r′ 使得 ai=x。只需输出 r′−l′+1 的最大值,若不存在则输出 0。
输入格式
第一行两个整数 n,m;
第二行 n 个整数依次表示 a1,…,an;
第三行 n 个整数依次表示 b1,…,bn;
接下来 m 行,每行 1,x,y 或 2,l,r,x 表示进行一次修改操作或查询操作。
1≤n,m≤106;
1≤ai≤n;
1≤bi≤n,bi 互不相同;
对修改操作,满足 1≤x,y≤n;
对查询操作,满足 1≤l≤r≤n,1≤x≤n;
输入的所有数值为整数。
输出格式
对每个查询操作,输出一行,表示相应的答案。
样例数据
样例输入
8 10
1 4 7 3 8 2 4 7
5 4 8 7 1 6 3 2
2 6 6 2
2 8 8 7
1 4 3
2 6 8 3
2 4 4 3
2 4 4 3
2 6 8 4
2 5 6 2
2 1 8 1
2 1 1 6
样例输出
1
1
0
1
1
3
2
1
0