struct node{
int data,lazy;
};
void build(const vector<int>&datas,vector<node>&tree,int rt,int left,int right){
if(left == right){
tree[rt].data=datas[left];
return;
}
int mid = left+(right-left)/2;
build(datas,tree,2*rt,left,mid);
build(datas,tree,2*rt+1,mid+1,right);
tree[rt].data = tree[2*rt].data+tree[2*rt+1].data;
}
void pushDown(vector<node>&tree,int rt, int len){
if(tree[rt].lazy != 0){
tree[rt*2].data += tree[rt].lazy * (len - len/2);
tree[rt*2].lazy += tree[rt].lazy;
tree[rt*2+1].data += tree[rt].lazy * (len/2);
tree[rt*2+1].lazy += tree[rt].lazy;
tree[rt].lazy = 0;
}
}
int query(vector<node>&tree,int rt,int left,int right,int ql,int qr){
if(ql > right || qr < left){
return MIN;
}
if(ql <= left && qr >= right){
return tree[rt].data;
}
int mid = left+(right-left)/2;
pushDown(tree,rt,right-left+1);
int leftsum = query(tree,2*rt,left,mid,ql,qr);
int rightsum = query(tree,2*rt+1,mid+1,right,ql,qr);
return leftsum+rightsum;
}
void updata(vector<node>&tree,int rt,int left,int right,int idx,int value){
if(left == right){
tree[rt].data = value;
tree[rt].lazy = 0;
return;
}
int mid = left+(right-left)/2;
pushDown(tree,rt,right-left+1);
if(idx<=mid){
updata(tree,2*rt,left,mid,idx,value);
}else{
updata(tree,2*rt+1,mid+1,right,idx,value);
}
tree[rt].data = tree[2*rt].data+tree[2*rt+1].data;
}
void updataRange(vector<node>&tree,int rt,int left,int right,int ul,int ur,int value){
if(ul>right||ur<left) return;
if(ul<=left && ur >= right){
tree[rt].data += value * (right - left + 1);
tree[rt].lazy += value;
return;
}
int mid = left+(right-left)/2;
pushDown(tree,rt,right-left+1);
updataRange(tree,2*rt,left,mid,ul,ur,value);
updataRange(tree,2*rt+1,mid+1,right,ul,ur,value);
tree[rt].data=tree[2*rt].data+tree[2*rt+1].data;
}template<class Info, class Tag> struct LazySegmentTree {
int n;
vector<Info> info;
vector<Tag> tag;
LazySegmentTree(vector<Info> init) {
n = init.size();
info.assign(4 * n, Info());
tag.assign(4 * n, Tag());
function<void(int, int, int)> build = [&](int p, int l, int r) {
if (l == r) {
info[p] = init[l - 1];
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m + 1, r);
pull(p);
};
build(1, 1, n);
}
void pull(int p) {
info[p] = info[2 * p] + info[2 * p + 1];
}
void apply(int p, const Tag &v) {
info[p].apply(v);
tag[p].apply(v);
}
void push(int p) {
apply(2 * p, tag[p]);
apply(2 * p + 1, tag[p]);
tag[p] = Tag();
}
void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
if (l > y || r < x) return;
if (l >= x && r <= y) {
apply(p, v);
return;
}
push(p);
int m = (l + r) / 2;
rangeApply(2 * p, l, m, x, y, v);
rangeApply(2 * p + 1, m + 1, r, x, y, v);
pull(p);
}
Info rangeQuery(int p, int l, int r, int x, int y) {
if (l > y || r < x) return Info();
if (l >= x && r <= y) return info[p];
push(p);
int m = (l + r) / 2;
return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m + 1, r, x, y);
}
};
struct Tag {
LL x;
Tag(LL x = 0) { this->x = x; }
void apply(const Tag &t) { x += t.x; }
};
struct Info {
LL x, l, r;
Info(LL x = 0, LL l = 0, LL r = 0) { this->x = x; this->l = l; this->r = r; }
void apply(const Tag &t) { if (t.x) x += t.x * (r - l + 1); }
};
Info operator+(const Info &a, const Info &b) { return Info(a.x + b.x, a.l, b.r); }struct tnode {
int l, r;
int mins;
};
struct Segment {
tnode t[4 * N];
int fa[4 * N];
void built(int root, int l, int r) {
"""
构建线段树
:param root: 当前节点
:param l: 左端点
:param r: 右端点
"""
t[root].l = l;
t[root].r = r;
if (l == r) {
t[root].mins = 0;
fa[l] = root;
return;
}
int ch = root << 1;
int mid = (l + r) >> 1;
built(ch, l, mid);
built(ch + 1, mid + 1, r);
t[root].mins = min(t[ch].mins, t[ch + 1].mins);
}
void modify(int num, int pos) {
"""
修改线段树
:param num: 要修改的位置
:param pos: 要修改的值
"""
int root = fa[num];
t[root].mins = pos;
root >>= 1;
while (root) {
int ch = root << 1;
t[root].mins = min(t[ch].mins, t[ch + 1].mins);
root >>= 1;
}
}
int query(int l) {
"""
查询线段树
:param l: 查询的左端点
:return: 最小的未被覆盖的位置
"""
int root = 1;
while (t[root].l != t[root].r) {
int ch = root << 1;
if (t[ch].mins >= l) {
root = ch + 1;
} else {
root = ch;
}
}
return t[root].l - 1;
}
} ST;
// int main() {
// // 初始化线段树,假设值范围是1到n
// int n;
// cin >> n;
// ST.built(1, 1, n);
// // 示例:处理m次操作
// int m;
// cin >> m;
// while (m--) {
// int op, x, y;
// cin >> op;
// if (op == 1) {
// cin >> x >> y;
// ST.modify(x, y);
// } else if (op == 2) {
// cin >> x;
// cout << ST.query(x) << '\n';
// }
// }
// }#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=1e5+3,inf=2147483647;
int i,j,n,k,m,a[N],lg[N],f1[N][18],f2[N][18];
int main(){
scanf("%d%d",&n,&k);
for(i=0;i<=17;i++)
for(j=0;j<=n+1;j++)
f1[i][j]=-inf,f2[i][j]=inf;
lg[1]=0;for(i=2;i<=n;i++)lg[i]=lg[i>>1]+1;m=lg[n];
for(i=1;i<=n;f2[i][0]=f1[i][0],i++)scanf("%d",&f1[i][0]);
for(i=1;i<=m;i++)
for(j=1;j+(1<<i)-1<=n;j++)
f1[j][i]=max(f1[j][i-1],f1[j+(1<<i-1)][i-1]),f2[j][i]=min(f2[j][i-1],f2[j+(1<<i-1)][i-1]);
m=lg[k];
for(i=1;i+k-1<=n;i++)printf("%d %d\n",max(f1[i][m],f1[i+k-(1<<m)][m]),min(f2[i][m],f2[i+k-(1<<m)][m]));
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=3e5+5,logN=19;
int n;char s[N];
inline void in(Re &x){
Re f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Suffix_Array{
int m,x[N],y[N],SA[N],cnt[N],rank[N],Height[N];
inline void get_SA(){
m=129;
for(Re i=1;i<=n;++i)++cnt[x[i]=s[i]];
for(Re i=2;i<=m;++i)cnt[i]+=cnt[i-1];
for(Re i=n;i>=1;--i)SA[cnt[x[i]]--]=i;
for(Re len=1;len<=n;len<<=1){
Re t=0;
for(Re i=n-len+1;i<=n;++i)y[++t]=i;
for(Re i=1;i<=n;++i)if(SA[i]>len)y[++t]=SA[i]-len;
for(Re i=1;i<=m;++i)cnt[i]=0;
for(Re i=1;i<=n;++i)++cnt[x[i]];
for(Re i=2;i<=m;++i)cnt[i]+=cnt[i-1];
for(Re i=n;i>=1;--i)SA[cnt[x[y[i]]]--]=y[i],y[i]=0;
swap(x,y),x[SA[1]]=m=1;
for(Re i=2;i<=n;++i)
x[SA[i]]=(y[SA[i]]==y[SA[i-1]]&&y[SA[i]+len]==y[SA[i-1]+len])?m:++m;
if(m>=n)break;
}
}
inline void get_Height(){
for(Re i=1;i<=n;++i)rank[SA[i]]=i;
for(Re i=1,k=0;i<=n;++i){
if(rank[i]==1)continue;
if(k)--k;
Re j=SA[rank[i]-1];
while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])++k;
Height[rank[i]]=k;
}
// for(Re i=1;i<=n;++i)printf("%d ",Height[i]);puts("");
}
int lg[N],dp[N][20];
inline void get_ST(){
lg[0]=-1;
for(Re i=1;i<=n;++i)dp[i][0]=Height[i],lg[i]=lg[i>>1]+1;
for(Re j=1;j<=logN;++j)
for(Re i=1;i+(1<<j)-1<=n;++i)
dp[i][j]=min(dp[i][j-1],dp[i+(1<<j-1)][j-1]);
}
inline int ask_min(Re l,Re r){
Re m=lg[r-l+1];
return min(dp[l][m],dp[r-(1<<m)+1][m]);
}
int r[N<<1];char a[N<<1];LL ans;
inline void check(Re x,Re len){
// printf("x=%d, len=%d\n",x,len);
x=rank[x];Re L=x,R=x;
if(Height[x]>=len){
Re l=2,r=x;
while(l<r){
Re mid=l+r>>1;
if(ask_min(mid,x)>=len)r=mid;
else l=mid+1;
}
L=r-1;
}
if(Height[x+1]>=len){
Re l=x+1,r=n;
while(l<r){
Re mid=l+r+1>>1;
if(ask_min(x+1,mid)>=len)l=mid;
else r=mid-1;
}
R=l;
}
ans=max(ans,(LL)len*(R-L+1));
}
inline void sakura(){
get_SA(),get_Height(),get_ST();
a[m=0]='$',a[++m]='|';
for(Re i=1;i<=n;++i)a[++m]=s[i],a[++m]='|';
for(Re i=1,R=0,mid=0;i<=m;++i){
r[i]=i<=R?min(r[(mid<<1)-i],R-i+1):1;
while(a[i-r[i]]==a[i+r[i]]){
++r[i];
if(i+r[i]-1>R)check((i>>1)-(r[i]>>1)+1,r[i]-!(i+r[i]&1));
}
if(i+r[i]-1>R)mid=i,R=i+r[i]-1;
}
// for(Re i=1;i<=m;++i)printf("%d ",r[i]);puts("");
printf("%lld\n",ans);
}
}SA;
int main(){
// freopen("123.txt","r",stdin);
// freopen("my.txt","w",stdout);
scanf("%s",s+1),n=strlen(s+1),SA.sakura();
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
int n,m,x,y,o,cnt,k[N],A[N],B[N],pt[N],head[N];LL b[N],dp[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Segment_Tree{
#define pl tr[p].lp
#define pr tr[p].rp
#define mid ((L+R)>>1)
int O;
struct QAQ{int id,lp,rp;}tr[N*18*2*2];
inline LL y(Re id,Re x){return (LL)k[id]*x+b[id];}
inline void change(Re &p,Re L,Re R,Re id){
if(!p){tr[p=++O].id=id;return;}
if(L==R){if(y(id,L)<y(tr[p].id,L))tr[p].id=id;return;}
if(k[id]>k[tr[p].id]){
if(y(id,mid)<y(tr[p].id,mid))change(pr,mid+1,R,tr[p].id),tr[p].id=id;
else change(pl,L,mid,id);
}
else{
if(y(id,mid)<y(tr[p].id,mid))change(pl,L,mid,tr[p].id),tr[p].id=id;
else change(pr,mid+1,R,id);
}
}
inline LL ask(Re p,Re L,Re R,Re x){
if(!p)return 1e18;
if(L==R)return y(tr[p].id,x);
LL ans=y(tr[p].id,x);
if(x<=mid)return min(ans,ask(pl,L,mid,x));
else return min(ans,ask(pr,mid+1,R,x));
}
inline int merge(Re p,Re q,Re L,Re R){
if(!p||!q)return p+q;
if(L==R){if(y(tr[p].id,L)>y(tr[q].id,L))tr[p].id=tr[q].id;return p;}
pl=merge(pl,tr[q].lp,L,mid);
pr=merge(pr,tr[q].rp,mid+1,R);
change(p,L,R,tr[q].id);
return p;
}
}TR;
inline void dfs(Re x,Re fa){
Re son=0;
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa)son=1,dfs(to,x),pt[x]=TR.merge(pt[x],pt[to],-N,N);
k[++cnt]=B[x],dp[x]=b[cnt]=son?TR.ask(pt[x],-N,N,A[x]):0;
TR.change(pt[x],-N,N,cnt);
}
int main(){
// freopen("123.txt","r",stdin);
in(n),m=n-1;
for(Re i=1;i<=n;++i)in(A[i]);
for(Re i=1;i<=n;++i)in(B[i]);
while(m--)in(x),in(y),add(x,y),add(y,x);
dfs(1,0);
for(Re i=1;i<=n;++i)printf("%lld\n",dp[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=2e5+3,logN=18;
int n,m,x,y,z,T,b[N],A[N],pt[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct President_Tree{
#define pl tr[p].lp
#define pr tr[p].rp
#define mid (L+R>>1)
int O;
struct QAQ{int S,lp,rp;}tr[N*(logN+1)];
inline void creat(Re &p,Re q,Re L,Re R,Re w){
p=++O,tr[p]=tr[q],++tr[p].S;
if(L==R)return;
if(w<=mid)creat(pl,tr[q].lp,L,mid,w);
else creat(pr,tr[q].rp,mid+1,R,w);
}
inline int ask(Re p,Re q,Re L,Re R,Re k){
if(L==R)return L;
Re tmp=tr[pl].S-tr[tr[q].lp].S;
if(tmp>=k)return ask(pl,tr[q].lp,L,mid,k);
else return ask(pr,tr[q].rp,mid+1,R,k-tmp);
}
}T1;
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T);
for(Re i=1;i<=n;++i)in(A[i]),b[i]=A[i];
sort(b+1,b+n+1),m=unique(b+1,b+n+1)-b-1;
for(Re i=1;i<=n;++i)T1.creat(pt[i],pt[i-1],1,m,lower_bound(b+1,b+m+1,A[i])-b);
while(T--)in(x),in(y),in(z),printf("%d\n",b[T1.ask(pt[y],pt[x-1],1,m,z)]);
}
#include<cstdio>
#define LL long long
#define Re register int
const int N=5e5+3;
int n,x,y,T;LL z,A[N];char op;
template<typename T>inline void in(T &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline LL abs(LL a){return a<0?-a:a;}
inline LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);}
struct BIT{
LL C[N];
inline void add(Re x,LL v){while(x<=n)C[x]+=v,x+=x&-x;}
inline void add(Re L,Re R,LL v){add(L,v),add(R+1,-v);}
inline LL ask(Re x){LL ans=0;while(x)ans+=C[x],x-=x&-x;return ans;}
}TR0;
struct Segment_Tree{
#define pl (p<<1)
#define pr (p<<1|1)
#define mid ((L+R)>>1)
LL tr[N<<2];
inline void pushup(Re p){tr[p]=gcd(tr[pl],tr[pr]);}
inline void build(Re p,Re L,Re R){
if(L==R){tr[p]=A[L]-A[L-1];return;}
build(pl,L,mid),build(pr,mid+1,R);
pushup(p);
}
inline void change(Re p,Re L,Re R,Re x,LL v){
if(L==R){tr[p]+=v;return;}
if(x<=mid)change(pl,L,mid,x,v);
else change(pr,mid+1,R,x,v);
pushup(p);
}
inline LL ask(Re p,Re L,Re R,Re l,Re r){
if(l<=L&&R<=r)return abs(tr[p]);
if(r<=mid)return ask(pl,L,mid,l,r);
else if(l>mid)return ask(pr,mid+1,R,l,r);
else return gcd(ask(pl,L,mid,l,r),ask(pr,mid+1,R,l,r));
}
}TR;
int main(){
in(n),in(T);
for(Re i=1;i<=n;++i)in(A[i]),TR0.add(i,i,A[i]);
TR.build(1,1,n);
while(T--){
scanf(" %c",&op),in(x),in(y);
if(op=='Q')printf("%lld\n",gcd(TR0.ask(x),TR.ask(1,1,n,x+1,y)));
else{
in(z),TR0.add(x,y,z),TR.change(1,1,n,x,z);if(y<n)TR.change(1,1,n,y+1,-z);
}
}
}
#include<cstdio>
#define LL long long
#define Re register int
const int N=1e5+3;
int n,x,y,z,T,op,A[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Segment_Tree{
#define pl (p<<1)
#define pr (p<<1|1)
#define mid ((L+R)>>1)
struct QAQ{LL S,add;}tr[N<<2];
inline void pushup(Re p){tr[p].S=tr[pl].S+tr[pr].S;}
inline void updata(Re p,Re L,Re R,LL v){tr[p].S+=v*(R-L+1),tr[p].add+=v;}
inline void pushdown(Re p,Re L,Re R){
if(tr[p].add)updata(pl,L,mid,tr[p].add),updata(pr,mid+1,R,tr[p].add),tr[p].add=0;
}
inline void build(Re p,Re L,Re R){
if(L==R){tr[p].S=A[L];return;}
build(pl,L,mid),build(pr,mid+1,R);
pushup(p);
}
inline void change(Re p,Re L,Re R,Re l,Re r,Re v){
if(l<=L&&R<=r){updata(p,L,R,v);return;}
pushdown(p,L,R);
if(l<=mid)change(pl,L,mid,l,r,v);
if(r>mid)change(pr,mid+1,R,l,r,v);
pushup(p);
}
inline LL ask(Re p,Re L,Re R,Re l,Re r){
if(l<=L&&R<=r)return tr[p].S;
LL ans=0;pushdown(p,L,R);
if(l<=mid)ans+=ask(pl,L,mid,l,r);
if(r>mid)ans+=ask(pr,mid+1,R,l,r);
return ans;
}
}TR;
int main(){
in(n),in(T);
for(Re i=1;i<=n;++i)in(A[i]);
TR.build(1,1,n);
while(T--){
in(op),in(x),in(y);
if(op<2)in(z),TR.change(1,1,n,x,y,z);
else printf("%lld\n",TR.ask(1,1,n,x,y));
}
}
#include<cstdio>
#define LL long long
#define Re register int
const int N=1e5+3;
int n,x,y,z,T,P,op,A[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Segment_Tree{
#define pl (p<<1)
#define pr (p<<1|1)
#define mid ((L+R)>>1)
struct QAQ{LL S,mul,add;}tr[N<<2];
inline void pushup(Re p){tr[p].S=(tr[pl].S+tr[pr].S)%P;}
inline void updata1(Re p,LL v){
tr[p].S=(LL)tr[p].S*v%P,tr[p].mul=(LL)tr[p].mul*v%P,tr[p].add=(LL)tr[p].add*v%P;
}
inline void updata2(Re p,Re L,Re R,LL v){(tr[p].S+=v*(R-L+1)%P)%=P,(tr[p].add+=v)%=P;}
inline void pushdown(Re p,Re L,Re R){
if(tr[p].mul!=1)updata1(pl,tr[p].mul),updata1(pr,tr[p].mul),tr[p].mul=1;
if(tr[p].add)updata2(pl,L,mid,tr[p].add),updata2(pr,mid+1,R,tr[p].add),tr[p].add=0;
}
inline void build(Re p,Re L,Re R){
tr[p].mul=1;
if(L==R){tr[p].S=A[L]%P;return;}
build(pl,L,mid),build(pr,mid+1,R);
pushup(p);
}
inline void change(Re p,Re L,Re R,Re l,Re r,Re v,Re op){
if(l<=L&&R<=r){if(op<2)updata1(p,v);else updata2(p,L,R,v);return;}
pushdown(p,L,R);
if(l<=mid)change(pl,L,mid,l,r,v,op);
if(r>mid)change(pr,mid+1,R,l,r,v,op);
pushup(p);
}
inline LL ask(Re p,Re L,Re R,Re l,Re r){
if(l<=L&&R<=r)return tr[p].S;
LL ans=0;pushdown(p,L,R);
if(l<=mid)(ans+=ask(pl,L,mid,l,r))%=P;
if(r>mid)(ans+=ask(pr,mid+1,R,l,r))%=P;
return ans;
}
}TR;
int main(){
in(n),in(T),in(P);
for(Re i=1;i<=n;++i)in(A[i]);
TR.build(1,1,n);
while(T--){
in(op),in(x),in(y);
if(op<3)in(z),TR.change(1,1,n,x,y,z,op);
else printf("%lld\n",TR.ask(1,1,n,x,y));
}
}
#include<algorithm>
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
#define div(a,b) floor((double)a/b)
using namespace std;
const int N=1e5+3;
int n,x,y,z,T,op,A[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Segment_Tree{
#define pl (p<<1)
#define pr (p<<1|1)
#define mid ((L+R)>>1)
struct QAQ{LL S,add,min,max;}tr[N<<2];
inline void pushup(Re p){
tr[p].S=tr[pl].S+tr[pr].S;
tr[p].min=min(tr[pl].min,tr[pr].min);
tr[p].max=max(tr[pl].max,tr[pr].max);
}
inline void updata(Re p,Re L,Re R,LL v){tr[p].S+=v*(R-L+1),tr[p].add+=v,tr[p].min+=v,tr[p].max+=v;}
inline void pushdown(Re p,Re L,Re R){
if(tr[p].add)updata(pl,L,mid,tr[p].add),updata(pr,mid+1,R,tr[p].add),tr[p].add=0;
}
inline void build(Re p,Re L,Re R){
if(L==R){tr[p].S=tr[p].min=tr[p].max=A[L];return;}
build(pl,L,mid),build(pr,mid+1,R);
pushup(p);
}
inline void change(Re p,Re L,Re R,Re l,Re r,Re v){
if(l<=L&&R<=r){updata(p,L,R,v);return;}
pushdown(p,L,R);
if(l<=mid)change(pl,L,mid,l,r,v);
if(r>mid)change(pr,mid+1,R,l,r,v);
pushup(p);
}
inline void change_div(Re p,Re L,Re R,Re l,Re r,Re v){
if(l<=L&&R<=r&&(div(tr[p].max,v)-tr[p].max==div(tr[p].min,v)-tr[p].min)){
updata(p,L,R,div(tr[p].max,v)-tr[p].max);return;
}
pushdown(p,L,R);
if(l<=mid)change_div(pl,L,mid,l,r,v);
if(r>mid)change_div(pr,mid+1,R,l,r,v);
pushup(p);
}
inline LL ask_min(Re p,Re L,Re R,Re l,Re r){
if(l<=L&&R<=r)return tr[p].min;
LL ans=1e18;pushdown(p,L,R);
if(l<=mid)ans=min(ans,ask_min(pl,L,mid,l,r));
if(r>mid)ans=min(ans,ask_min(pr,mid+1,R,l,r));
return ans;
}
inline LL ask_S(Re p,Re L,Re R,Re l,Re r){
if(l<=L&&R<=r)return tr[p].S;
LL ans=0;pushdown(p,L,R);
if(l<=mid)ans+=ask_S(pl,L,mid,l,r);
if(r>mid)ans+=ask_S(pr,mid+1,R,l,r);
return ans;
}
}TR;
int main(){
in(n),in(T);
for(Re i=1;i<=n;++i)in(A[i]);
TR.build(1,1,n);
while(T--){
in(op),in(x),in(y),++x,++y;
if(op<2)in(z),TR.change(1,1,n,x,y,z);
else if(op<3)in(z),TR.change_div(1,1,n,x,y,z);
else if(op<4)printf("%lld\n",TR.ask_min(1,1,n,x,y));
else printf("%lld\n",TR.ask_S(1,1,n,x,y));
}
}
#include<algorithm>
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
int n,x,y,z,T,op;LL A[N];
template<typename T>inline void in(T &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Segment_Tree{
#define pl (p<<1)
#define pr (p<<1|1)
#define mid ((L+R)>>1)
struct QAQ{LL S,max;}tr[N<<2];
inline void pushup(Re p){
tr[p].S=tr[pl].S+tr[pr].S;
tr[p].max=max(tr[pl].max,tr[pr].max);
}
inline void build(Re p,Re L,Re R){
if(L==R){tr[p].S=tr[p].max=A[L];return;}
build(pl,L,mid),build(pr,mid+1,R);
pushup(p);
}
inline void change(Re p,Re L,Re R,Re l,Re r){
if(tr[p].max<=1)return;
if(L==R){tr[p].max=tr[p].S=sqrt(tr[p].S);return;}
if(l<=mid)change(pl,L,mid,l,r);
if(r>mid)change(pr,mid+1,R,l,r);
pushup(p);
}
inline LL ask(Re p,Re L,Re R,Re l,Re r){
if(l<=L&&R<=r)return tr[p].S;
LL ans=0;
if(l<=mid)ans+=ask(pl,L,mid,l,r);
if(r>mid)ans+=ask(pr,mid+1,R,l,r);
return ans;
}
}TR;
int main(){
in(n);
for(Re i=1;i<=n;++i)in(A[i]);
TR.build(1,1,n),in(T);
while(T--){
in(op),in(x),in(y);if(x>y)swap(x,y);
if(op)printf("%lld\n",TR.ask(1,1,n,x,y));
else TR.change(1,1,n,x,y);
}
}
#include<algorithm>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=5e4+3;
int n,x,y,T,op,A[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Segment_Tree{
#define pl (p<<1)
#define pr (p<<1|1)
#define mid ((L+R)>>1)
struct QAQ{LL S,max,lmax,rmax;}tr[N<<2];
inline void pushup(QAQ &A,const QAQ &L,const QAQ &R){
A.S=L.S+R.S;
A.lmax=max(L.lmax,L.S+R.lmax);
A.rmax=max(R.rmax,R.S+L.rmax);
A.max=max(max(max(L.max,R.max),max(A.lmax,A.rmax)),L.rmax+R.lmax);
}
inline void change(Re p,Re L,Re R,Re x,Re v){
if(L==R){tr[p].S=tr[p].max=tr[p].lmax=tr[p].rmax=v;return;}
if(x<=mid)change(pl,L,mid,x,v);
else change(pr,mid+1,R,x,v);
pushup(tr[p],tr[pl],tr[pr]);
}
inline QAQ ask(Re p,Re L,Re R,Re l,Re r){
if(l<=L&&R<=r)return tr[p];
if(r<=mid)return ask(pl,L,mid,l,r);
else if(l>mid)return ask(pr,mid+1,R,l,r);
else{QAQ ans;pushup(ans,ask(pl,L,mid,l,r),ask(pr,mid+1,R,l,r));return ans;}
}
}TR;
int main(){
in(n);
for(Re i=1;i<=n;++i)in(A[i]),TR.change(1,1,n,i,A[i]);
in(T);
while(T--){
in(op),in(x),in(y);
if(op)printf("%lld\n",TR.ask(1,1,n,x,y).max);
else TR.change(1,1,n,x,y);
}
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=6003;
int n,m,x,y,t,o,Ans,b[N],A[N],pt[N],head[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Segment_Tree{
#define pl (tr[p].lp)
#define pr (tr[p].rp)
#define mid ((L+R)>>1)
int O;
struct QAQ{int lp,rp,up,down;}tr[N*13*2];
inline void pushup(Re p){
tr[p].up=max(tr[pl].up,tr[pr].up);
tr[p].down=max(tr[pl].down,tr[pr].down);
}
inline void change1(Re &p,Re L,Re R,Re x,Re v){
if(!p)p=++O;
if(L==R){tr[p].up=max(tr[p].up,v);return;}
if(x<=mid)change1(pl,L,mid,x,v);
else change1(pr,mid+1,R,x,v);
pushup(p);
}
inline void change2(Re &p,Re L,Re R,Re x,Re v){
if(!p)p=++O;
if(L==R){tr[p].down=max(tr[p].down,v);return;}
if(x<=mid)change2(pl,L,mid,x,v);
else change2(pr,mid+1,R,x,v);
pushup(p);
}
inline int ask1(Re p,Re L,Re R,Re l,Re r){
if(!p)return 0;
if(l<=L&&R<=r)return tr[p].up;
Re ans=0;
if(l<=mid)ans=max(ans,ask1(pl,L,mid,l,r));
if(r>mid)ans=max(ans,ask1(pr,mid+1,R,l,r));
return ans;
}
inline int ask2(Re p,Re L,Re R,Re l,Re r){
if(!p)return 0;
if(l<=L&&R<=r)return tr[p].down;
Re ans=0;
if(l<=mid)ans=max(ans,ask2(pl,L,mid,l,r));
if(r>mid)ans=max(ans,ask2(pr,mid+1,R,l,r));
return ans;
}
inline int merge(Re p,Re q,Re L,Re R){
if(!p||!q)return p+q;
if(L==R){tr[p].up=max(tr[p].up,tr[q].up),tr[p].down=max(tr[p].down,tr[q].down);return p;}
Ans=max(Ans,max(tr[pl].up+tr[tr[q].rp].down,tr[pr].down+tr[tr[q].lp].up));
pl=merge(pl,tr[q].lp,L,mid);
pr=merge(pr,tr[q].rp,mid+1,R);
pushup(p);return p;
}
}TR;
inline void dfs(Re x,Re fa){
Re up=0,down=0;
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa){
dfs(to,x);
Re tmp1=TR.ask1(pt[to],1,t,1,A[x]-1),tmp2=TR.ask2(pt[to],1,t,A[x]+1,t);
Ans=max(Ans,max(up+tmp2+1,down+tmp1+1));
up=max(up,tmp1),down=max(down,tmp2);
pt[x]=TR.merge(pt[x],pt[a[i].to],1,t);
}
TR.change1(pt[x],1,t,A[x],up+1),TR.change2(pt[x],1,t,A[x],down+1);
}
int main(){
// freopen("123.txt","r",stdin);
in(n),m=n-1;
for(Re i=1;i<=n;++i)in(A[i]),b[i]=A[i];
sort(b+1,b+n+1),t=unique(b+1,b+n+1)-b;
for(Re i=1;i<=n;++i)A[i]=lower_bound(b+1,b+t+1,A[i])-b;
while(m--)in(x),in(y),add(x,y),add(y,x);
dfs(1,0),printf("%d\n",Ans);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=2e5+3;char opt[N];
int x,y,z,w,n,T,op,A[N],rk[N];
inline void in(int &x){
Re fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
int pt[N<<1];
struct Segment_Tree{
#define pl tr[p].lp
#define pr tr[p].rp
#define mid ((L+R)>>1)
int O;queue<int>Q;
struct QAQ{int S,lp,rp;}tr[N*200];
inline int New(){// 新建节点
if(Q.empty())return ++O;
Re tmp=Q.front();Q.pop();
return tmp;
}
inline void del(Re &p){pl=pr=0,Q.push(p),p=0;}// 删除节点(注意取地址,初始化为1)
inline void change(Re &p,Re L,Re R,Re w,Re v){
if(!p)p=New();tr[p].S+=v;
if(L==R){if(!tr[p].S)del(p);return;}
if(w<=mid)change(pl,L,mid,w,v);
else change(pr,mid+1,R,w,v);
if(!tr[p].S)del(p);
}
inline int ask(Re p,Re L,Re R,Re l,Re r){
if(!p)return 0;
if(l<=L&&R<=r)return tr[p].S;
Re ans=0;
if(l<=mid)ans+=ask(pl,L,mid,l,r);
if(r>mid)ans+=ask(pr,mid+1,R,l,r);
return ans;
}
}TR;
inline int ask(Re L,Re R,Re l,Re r){
Re ans=0;
for(Re i=R;i;i-=i&-i)ans+=TR.ask(pt[i],1,n,l,r);
for(Re i=L-1;i;i-=i&-i)ans-=TR.ask(pt[i],1,n,l,r);
return ans;
}
inline void add(Re x,Re w,Re v){
for(Re i=x;i<=n;i+=i&-i)TR.change(pt[i],1,n,w,v);
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T);
for(Re i=1;i<=n;++i)in(x),rk[x]=i;
for(Re i=1;i<=n;++i)in(A[i]),A[i]=rk[A[i]],add(i,A[i],1);
while(T--){
in(op),in(x),in(y);
if(op>1)add(x,A[x],-1),add(y,A[y],-1),swap(A[x],A[y]),add(x,A[x],1),add(y,A[y],1);
else in(z),in(w),printf("%d\n",ask(z,w,x,y));
}
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
int n,m,T,b[N<<1],A[N];char op[N];
struct QWQ{int x,y,k;}Q[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
int t1,t2,pt[N],ptl[20],ptr[20];
struct President_Tree{
#define pl (tr[p].lp)
#define pr (tr[p].rp)
#define mid ((L+R)>>1)
int O;
struct QAQ{int S,lp,rp;}tr[(N<<1)*200];
inline void change(Re &p,Re L,Re R,Re x,Re v){
if(!p)p=++O;tr[p].S+=v;
if(L==R)return;
if(x<=mid)change(pl,L,mid,x,v);
else change(pr,mid+1,R,x,v);
}
inline int ask(Re p,Re L,Re R,Re K){
if(L==R)return L;
Re tmp=0;
for(Re i=1;i<=t1;++i)tmp-=tr[tr[ptl[i]].lp].S;
for(Re i=1;i<=t2;++i)tmp+=tr[tr[ptr[i]].lp].S;
if(K<=tmp){
for(Re i=1;i<=t1;++i)ptl[i]=tr[ptl[i]].lp;
for(Re i=1;i<=t2;++i)ptr[i]=tr[ptr[i]].lp;
return ask(pl,L,mid,K);
}
else{
for(Re i=1;i<=t1;++i)ptl[i]=tr[ptl[i]].rp;
for(Re i=1;i<=t2;++i)ptr[i]=tr[ptr[i]].rp;
return ask(pr,mid+1,R,K-tmp);
}
}
}SG;
struct BIT{
inline void add(Re x,Re v){
for(Re i=x;i<=n;i+=i&-i)SG.change(pt[i],1,m,A[x],v);
}
inline int ask(Re L,Re R,Re k){
t1=t2=0;
for(Re i=L-1;i;i-=i&-i)ptl[++t1]=pt[i];
for(Re i=R;i;i-=i&-i)ptr[++t2]=pt[i];
return SG.ask(1,1,m,k);
}
}TR;
int main(){
in(n),in(T),m=n;
for(Re i=1;i<=n;++i)in(A[i]),b[i]=A[i];
for(Re i=1;i<=T;++i){
scanf(" %c",&op[i]),in(Q[i].x),in(Q[i].y);
if(op[i]=='Q')in(Q[i].k);
else b[++m]=Q[i].y;
}
sort(b+1,b+m+1),m=unique(b+1,b+m+1)-b-1;
for(Re i=1;i<=n;++i)A[i]=lower_bound(b+1,b+m+1,A[i])-b;
for(Re i=1;i<=T;++i)if(op[i]=='C')Q[i].y=lower_bound(b+1,b+m+1,Q[i].y)-b;
for(Re i=1;i<=n;++i)TR.add(i,1);
for(Re i=1;i<=T;++i){
if(op[i]=='Q')printf("%d\n",b[TR.ask(Q[i].x,Q[i].y,Q[i].k)]);
else TR.add(Q[i].x,-1),A[Q[i].x]=Q[i].y,TR.add(Q[i].x,1);
}
}
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=2e4+3,M=5e4+3;
int n,m,x,y,z,T,op,X[N+M],Y[N+M],last[M];LL v[N+M],Ans[M];
inline void in(int &x){
Re fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct QWQ{int id,op;QWQ(Re ID=0,Re OP=0){id=ID,op=OP;}};
struct Link_Cut_Tree{
#define pl tr[p].ps[0]
#define pr tr[p].ps[1]
#define pf tr[p].fa
int size,Q[N+M];QWQ QQ[M*32];LL MST;
struct QAQ{int mx,fa,tag,ps[2];}tr[N+M];
inline void pushup(Re p){
tr[p].mx=p;
if(pl&&v[tr[pl].mx]>v[tr[p].mx])tr[p].mx=tr[pl].mx;
if(pr&&v[tr[pr].mx]>v[tr[p].mx])tr[p].mx=tr[pr].mx;
}
inline void updata(Re p){swap(pl,pr),tr[p].tag^=1;}
inline void pushdown(Re p){
if(tr[p].tag){
if(pl)updata(pl);
if(pr)updata(pr);
tr[p].tag=0;
}
}
inline int which(Re p){return tr[pf].ps[1]==p;}
inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
inline void rotate(Re p){
Re fa=pf,fas=which(p);
Re pa=tr[fa].fa,pas=which(fa);
Re x=tr[p].ps[fas^1];
if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
connect(x,fa,fas),connect(fa,p,fas^1);
pushup(fa),pushup(p);
}
inline void splay(Re p){
Re x=p,t=0;Q[++t]=x;
while(nort(x))Q[++t]=x=tr[x].fa;
while(t)pushdown(Q[t--]);
for(Re fa;nort(p);rotate(p))
if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
}
inline void access(Re p){
for(Re son=0;p;son=p,p=pf)
splay(p),pr=son,pushup(p);
}
inline void makeroot(Re x){access(x),splay(x),updata(x);}
inline int findroot(Re p){
access(p),splay(p),pushdown(p);
while(pl)pushdown(p=pl);
return p;
}
inline void split(Re x,Re y){makeroot(x),access(y),splay(y);}
inline void link(Re x,Re y){makeroot(x),tr[x].fa=y;}
inline void cut(Re x,Re y){makeroot(x),access(y),splay(y),tr[x].fa=tr[y].ps[0]=0,pushup(y);}
inline void cut_(Re id){
makeroot(Y[id]),access(X[id]),splay(X[id]),tr[X[id]].ps[0]=tr[Y[id]].fa=tr[id].ps[0]=tr[id].fa=0,pushup(X[id]);
}
inline void link_(Re id){
makeroot(X[id]),makeroot(Y[id]),tr[X[id]].fa=tr[Y[id]].fa=id;
}
inline void MST_link(Re id){
Re x=X[id],y=Y[id];makeroot(x);
if(findroot(y)!=x)link(x,id),link(id,y),QQ[++size]=QWQ(id,0),MST+=v[id];
else{
Re mx=tr[y].mx;
if(v[id]<v[mx]){
// cut(X[mx],mx),cut(mx,Y[mx]),QQ[++size]=QWQ(mx,1);
cut_(mx),QQ[++size]=QWQ(mx,1);
link(x,id),link(id,y),QQ[++size]=QWQ(id,0);
// link_(id),QQ[++size]=QWQ(id,0);
MST+=v[id]-v[mx];
}
}
}
inline void back(Re to){
while(size>to){
QWQ a=QQ[size--];Re id=a.id;
if(a.op)link(id,Y[id]),link(X[id],id),MST+=v[id];
// else cut(id,Y[id]),cut(X[id],id),MST-=v[id];
// if(a.op)link_(id),MST+=v[id];
else cut_(id),MST-=v[id];
}
}
#undef pl
#undef pr
}LCT;
int o,head[M<<2];
struct QAQ{int id,next;LL v;}a[M*32];
inline void add(Re x,Re id,LL v){a[++o].id=id,a[o].v=v,a[o].next=head[x],head[x]=o;}
struct Segment_Tree{
#define pl (p<<1)
#define pr (p<<1|1)
#define mid ((L+R)>>1)
inline void change(Re p,Re L,Re R,Re l,Re r,Re id,LL v){
if(l>r)return;
if(l<=L&&R<=r){add(p,id,v);return;}
if(l<=mid)change(pl,L,mid,l,r,id,v);
if(r>mid)change(pr,mid+1,R,l,r,id,v);
}
inline void dfs(Re p,Re L,Re R){
Re tmp=LCT.size;
for(Re i=head[p];i;i=a[i].next)v[a[i].id]=a[i].v,LCT.MST_link(a[i].id);
if(L==R)Ans[L]=LCT.MST;
else dfs(pl,L,mid),dfs(pr,mid+1,R);
LCT.back(tmp);
}
}T1;
int main(){
// freopen("123.txt","r",stdin);
// freopen("my.txt","w",stdout);
in(n),in(m),in(T);
for(Re i=1;i<=m;++i)in(X[i+n]),in(Y[i+n]),in(x),v[i+n]=x,last[i]=1;
for(Re i=1;i<=T;++i){
in(x),in(y);
T1.change(1,1,T,last[x],i-1,x+n,v[x+n]);
last[x]=i,v[x+n]=y;
}
for(Re i=1;i<=m;++i)T1.change(1,1,T,last[i],T,i+n,v[i+n]);
T1.dfs(1,1,T);
for(Re i=1;i<=T;++i)printf("%lld\n",Ans[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<stack>
#include<map>
#define LL long long
#define Re register int
#define mp make_pair
using namespace std;
const int N=1e5+3,M=2e5+3;
int x,y,l,r,n,m,T,Ans[N];char ch[20];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Union{// 冰茶姬(并查集)
struct BK{int x,y,sizex,sizey;BK(Re X=0,Re S1=0,Re Y=0,Re S2=0){x=X,y=Y,sizex=S1,sizey=S2;}};
int fa[N<<1],size[N<<1];stack<BK>Q;
inline int find(Re x){return fa[x]==x?x:find(fa[x]);}
inline void merge(Re x,Re y){// 启发式合并
x=find(x),y=find(y);
if(x==y)return;
if(size[x]>size[y])swap(x,y);
Q.push(BK(x,size[x],y,size[y]));
fa[x]=y,size[y]+=size[x];
}
inline void back(Re to){// 撤销操作
while(int(Q.size())>to){
BK a=Q.top();Q.pop();
fa[a.x]=a.x,size[a.x]=a.sizex;
fa[a.y]=a.y,size[a.y]=a.sizey;
}
}
}TF;
int o,head[N<<2];
struct QAQ{int x,y,next;}a[M*20];
inline void add(Re x,Re y1,Re y2){a[++o].x=y1,a[o].y=y2,a[o].next=head[x],head[x]=o;}
struct Segment_Tree{
#define pl (p<<1)
#define pr (p<<1|1)
#define mid ((L+R)>>1)
inline void change(Re p,Re L,Re R,Re l,Re r,Re x,Re y){
if(l>r)return;
if(l<=L&&R<=r){add(p,x,y);return;}
if(l<=mid)change(pl,L,mid,l,r,x,y);
if(r>mid)change(pr,mid+1,R,l,r,x,y);
}
inline void dfs(Re p,Re L,Re R){
Re tmp=TF.Q.size();
for(Re i=head[p];i;i=a[i].next){
if(TF.find(a[i].x)==TF.find(a[i].y)){
for(Re j=L;j<=R;++j)Ans[j]=1;
TF.back(tmp);return;
}
TF.merge(a[i].x,a[i].y+n),TF.merge(a[i].x+n,a[i].y);
}
if(L<R)dfs(pl,L,mid),dfs(pr,mid+1,R);
TF.back(tmp);
}
}T1;
int main(){
// freopen("123.txt","r",stdin);
in(n),in(m),in(T);
for(Re i=1;i<=(n<<1);++i)TF.fa[i]=i,TF.size[i]=1;
for(Re i=1;i<=m;++i)in(x),in(y),in(l),in(r),T1.change(1,1,T,l+1,r+1-1,x,y);
T1.dfs(1,1,T);
for(Re i=1;i<=T;++i)puts(Ans[i]?"No":"Yes");
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<stack>
#include<map>
#define LL long long
#define Re register int
#define mp(x,y) make_pair(x,y)
using namespace std;
const int N=1e4+3,M=2e5+3;
int x,y,n,T,Ans[M];char ch[20];
map<pair<int,int>,int>last;
struct Query{int x,y,op;}Q[M];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Union{// 冰茶姬(并查集)
struct BK{int x,y,sizex,sizey;BK(Re X=0,Re S1=0,Re Y=0,Re S2=0){x=X,y=Y,sizex=S1,sizey=S2;}};
int fa[N],size[N];stack<BK>Q;
inline int find(Re x){return fa[x]==x?x:find(fa[x]);}
inline void merge(Re x,Re y){// 启发式合并
x=find(x),y=find(y);
if(size[x]>size[y])swap(x,y);
Q.push(BK(x,size[x],y,size[y]));
fa[x]=y,size[y]+=size[x];
}
inline void back(Re to){// 撤销操作
while(Q.size()>to){
BK a=Q.top();Q.pop();
fa[a.x]=a.x,size[a.x]=a.sizex;
fa[a.y]=a.y,size[a.y]=a.sizey;
}
}
}TF;
int o,head[M<<2];
struct QAQ{int x,y,next;}a[M*20];
inline void add(Re x,Re y1,Re y2){a[++o].x=y1,a[o].y=y2,a[o].next=head[x],head[x]=o;}
struct Segment_Tree{
#define pl (p<<1)
#define pr (p<<1|1)
#define mid (L+R>>1)
inline void change(Re p,Re L,Re R,Re l,Re r,Re x,Re y){
if(l<=L&&R<=r){add(p,x,y);return;}
if(l<=mid)change(pl,L,mid,l,r,x,y);
if(r>mid)change(pr,mid+1,R,l,r,x,y);
}
inline void dfs(Re p,Re L,Re R){
Re tmp=TF.Q.size();
for(Re i=head[p];i;i=a[i].next)TF.merge(a[i].x,a[i].y);
if(L==R){if(Q[L].op)Ans[L]=(TF.find(Q[L].x)==TF.find(Q[L].y));}
else dfs(pl,L,mid),dfs(pr,mid+1,R);
TF.back(tmp);
}
}T1;
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T);
for(Re i=1;i<=n;++i)TF.fa[i]=i,TF.size[i]=1;
for(Re i=1;i<=T;++i){
scanf("%s",ch),in(x),in(y);if(x>y)swap(x,y);
if(ch[0]=='Q')Q[i].op=1,Q[i].x=x,Q[i].y=y;
else if(ch[0]=='C')last[mp(x,y)]=i;
else T1.change(1,1,T,last[mp(x,y)],i,x,y),last.erase(mp(x,y));
}
for(map<pair<int,int>,int>::iterator it=last.begin();it!=last.end();++it)
T1.change(1,1,T,it->second,T,it->first.first,it->first.second);
T1.dfs(1,1,T);
for(Re i=1;i<=T;++i)if(Q[i].op)puts(Ans[i]?"Yes":"No");
}
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<bitset>
#include<stack>
#define LL long long
#define Re register int
#define Int bitset<M>
using namespace std;
const int N=550+5,M=1000+5;
int n,m,x,y,o,O,T,logN,X[N],Y[N],fa[N],last[N],head[N];Int z,Z[N],dis[N],Ans[M];char op[20];
struct QAQ{int to,next;Int w;}a[N<<1];
inline void add(Re x,Re y,Int z){a[++o].to=y,a[o].w=z,a[o].next=head[x],head[x]=o;}
inline int find(Re x){return x==fa[x]?x:fa[x]=find(fa[x]);}
inline int getlen(Int &x){Re n=1000;while(n>=1&&!x[n])--n;return n;}
inline void print(Int &x){for(Re i=getlen(x);i>=0;--i)putchar(x[i]+'0');puts("");}
inline void in(Int &x){cin>>x,logN=max(logN,getlen(x));}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Line_JI{
Int p[M];bool pp[M];stack<int>Q;
inline void insert(Int x){
for(Re i=logN;i>=0;--i)
if(x[i]){
if(!pp[i]){Q.push(i),p[i]=x,pp[i]=1;break;}
x^=p[i];
}
}
inline Int ask(){
Int ans;ans.reset();
for(Re i=logN;i>=0;--i)if(pp[i]&&(!ans[i]))ans^=p[i];
return ans;
}
inline void back(Re to){
while(Q.size()>to)x=Q.top(),Q.pop(),p[x].reset(),pp[x]=0;
}
}JI;
struct Segment_Tree{
int o,head[M<<2];
struct QAQ{int x,y,next;Int w;}a[(N+M)*10];
inline void add(Re t,Re x,Re y,Int &z){a[++o].x=x,a[o].y=y,a[o].w=z,a[o].next=head[t],head[t]=o;}
#define pl (p<<1)
#define pr (p<<1|1)
#define mid ((L+R)>>1)
inline void change(Re p,Re L,Re R,Re l,Re r,Re x,Re y,Int &z){
if(l<=L&&R<=r){add(p,x,y,z);return;}
if(l<=mid)change(pl,L,mid,l,r,x,y,z);
if(r>mid)change(pr,mid+1,R,l,r,x,y,z);
}
inline void dfs(Re p,Re L,Re R){
Re tmp=JI.Q.size();
for(Re i=head[p];i;i=a[i].next)JI.insert(dis[a[i].x]^dis[a[i].y]^a[i].w);
if(L==R)Ans[L]=JI.ask();// 这里还没做back撤销操作,不能return!!!
else dfs(pl,L,mid),dfs(pr,mid+1,R);
JI.back(tmp);
}
}TR;
inline void dfs(Re x,Re fa,Re w){
dis[x]=dis[fa]^a[w].w;
for(Re i=head[x];i;i=a[i].next)
if(a[i].to!=fa)dfs(a[i].to,x,i);
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(m),in(T),++T;
for(Re i=1;i<=n;++i)fa[i]=i;
while(m--){
in(x),in(y),in(z);
if(find(x)!=find(y))add(x,y,z),add(y,x,z),fa[find(x)]=find(y);
else TR.change(1,1,T,1,T,x,y,z);
}
for(Re i=2;i<=T;++i){
scanf("%s",op);
if(op[0]=='A')last[++O]=i,in(X[O]),in(Y[O]),in(Z[O]);
else if(op[1]=='h'){
in(x),in(z);
TR.change(1,1,T,last[x],i-1,X[x],Y[x],Z[x]);
last[x]=i,Z[x]=z;
}
else in(x),TR.change(1,1,T,last[x],i-1,X[x],Y[x],Z[x]),last[x]=0;
}
for(Re i=1;i<=O;++i)if(last[i])TR.change(1,1,T,last[i],T,X[i],Y[i],Z[i]);
dfs(1,0,0),TR.dfs(1,1,T);
for(Re i=1;i<=T;++i)print(Ans[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#define LL long long
#define Re register int
#define IT set<QAQ>::iterator
using namespace std;
const int N=1e5+3;
int n,m,l,r,T,op,A[N],tmp[N],cnt[N],Ans[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct QAQ{
int l,r;mutable int pt,op;
QAQ(Re L=0,Re R=0,Re OP=0,Re PT=0){l=L,r=R,op=OP,pt=PT;};
inline bool operator<(const QAQ &O)const{return l<O.l;}
};
set<QAQ>s;
struct Segment_Tree{
#define pl tr[p].lp
#define pr tr[p].rp
#define mid ((L+R)>>1)
int O;
struct QAQ{int S,lp,rp;}tr[N*60];
inline void pushup(Re p){tr[p].S=tr[pl].S+tr[pr].S;}
inline void change(Re &p,Re L,Re R,Re x){
p=++O;
if(L==R){tr[p].S=1;return;}
if(x<=mid)change(pl,L,mid,x);
else change(pr,mid+1,R,x);
pushup(p);
}
inline int merge(Re p,Re q,Re L,Re R){
if(!p||!q)return p+q;
if(L==R){tr[p].S+=tr[q].S;return p;}
pl=merge(pl,tr[q].lp,L,mid);
pr=merge(pr,tr[q].rp,mid+1,R);
pushup(p);return p;
}
inline void split1(Re &p,Re q,Re L,Re R,Re k){// 取q中的前k个,分到新节点p
tr[p=++O].S=tr[q].S-k,tr[q].S=k;
if(L==R)return;
Re tmp=tr[tr[q].lp].S;
if(k>tmp)split1(pr,tr[q].rp,mid+1,R,k-tmp);// q左子树全部分给p,只剩右子树
else pr=tr[q].rp,tr[q].rp=0;// 右子树全部分给p
if(k<tmp)split1(pl,tr[q].lp,L,mid,k);// q的右子树全部分给p,只剩左子树
}
inline void split2(Re &p,Re q,Re L,Re R,Re k){// 取q中的后k个,分到新节点p
tr[p=++O].S=tr[q].S-k,tr[q].S=k;
if(L==R)return;
Re tmp=tr[tr[q].rp].S;
if(k>tmp)split2(pl,tr[q].lp,L,mid,k-tmp);// q的右子树全部分给p,只剩左子树
else pl=tr[q].lp,tr[q].lp=0;// 左子树全部分给p
if(k<tmp)split2(pr,tr[q].rp,mid+1,R,k);// q左子树全部分给p,只剩右子树
}
inline void dfs(Re p,Re L,Re R){
if(!p)return;
if(L==R){cnt[tmp[++tmp[0]]=L]=tr[p].S;return;}
dfs(pl,L,mid),dfs(pr,mid+1,R);
}
}T1;
inline IT split(Re w){
IT it=s.lower_bound(QAQ(w));
if(it!=s.end()&&it->l==w)return it;
--it;
Re L=it->l,R=it->r,op=it->op,pt=it->pt,ptt=0;
s.erase(it);
if(op)T1.split1(ptt,pt,1,m,w-1-L+1);
else T1.split2(ptt,pt,1,m,w-1-L+1);
s.insert(QAQ(L,w-1,op,pt));
return s.insert(QAQ(w,R,op,ptt)).first;
}
inline void assign(Re l,Re r,Re op){
if(l==r)return;
IT itr=split(r+1),itl=split(l),it=itl;
Re pt=0;
while(it!=itr)pt=T1.merge(pt,it->pt,1,m),it->pt=0,++it;
s.erase(itl,itr),s.insert(QAQ(l,r,op,pt));
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T),m=n;
for(Re i=1;i<=n;++i)in(A[i]);
s.insert(QAQ(n+1,n+1));
for(Re i=1;i<=n;++i){
QAQ tmp(i,i,0,0);T1.change(tmp.pt,1,m,A[i]),s.insert(tmp);
}
while(T--)in(op),in(l),in(r),op^=1,assign(l,r,op);
IT itl=s.lower_bound(QAQ(1)),itr=s.lower_bound(QAQ(n+1));
while(itl!=itr){
tmp[0]=0,T1.dfs(itl->pt,1,m);
if(itl->op)for(Re i=1;i<=tmp[0];++i)
for(Re j=1;j<=cnt[tmp[i]];++j)
Ans[++Ans[0]]=tmp[i];
else for(Re i=tmp[0];i>=1;--i)
for(Re j=1;j<=cnt[tmp[i]];++j)
Ans[++Ans[0]]=tmp[i];
++itl;
}
in(op),printf("%d\n",Ans[op]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=2e5+3;
int n,m,x,y,p,T,op,A[N],pt[N];LL K;
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Segment_Tree{
#define pl tr[p].lp
#define pr tr[p].rp
#define mid ((L+R)>>1)
int O;
struct QAQ{int lp,rp;LL S;}tr[N*20];
inline void pushup(Re p){tr[p].S=tr[pl].S+tr[pr].S;}
inline void build(Re &p,Re L,Re R){
p=++O;
if(L==R){tr[p].S=A[L];return;}
build(pl,L,mid),build(pr,mid+1,R);
pushup(p);
}
inline void change(Re &p,Re L,Re R,Re x,Re v){
if(!p)p=++O;
if(L==R){tr[p].S+=v;return;}
if(x<=mid)change(pl,L,mid,x,v);
else change(pr,mid+1,R,x,v);
pushup(p);
}
inline LL ask(Re p,Re L,Re R,Re l,Re r){
if(!p)return 0;
if(l<=L&&R<=r)return tr[p].S;
LL ans=0;
if(l<=mid)ans+=ask(pl,L,mid,l,r);
if(r>mid)ans+=ask(pr,mid+1,R,l,r);
return ans;
}
inline int ask(Re p,Re L,Re R,LL k){
if(!p||k>tr[p].S)return -1;
if(L==R)return L;
LL tmp=tr[pl].S;
if(tmp>=k)return ask(pl,L,mid,k);
else return ask(pr,mid+1,R,k-tmp);
}
inline int merge(Re p,Re q,Re L,Re R){
if(!p||!q)return p+q;
if(L==R){tr[p].S+=tr[q].S;return p;}
pl=merge(pl,tr[q].lp,L,mid);
pr=merge(pr,tr[q].rp,mid+1,R);
pushup(p);return p;
}
inline void split(Re &p,Re &q,Re L,Re R,Re l,Re r){
if(!q)return;
if(l<=L&&R<=r){p=q,q=0;return;}
p=++O;
if(l<=mid)split(pl,tr[q].lp,L,mid,l,r);
if(r>mid)split(pr,tr[q].rp,mid+1,R,l,r);
pushup(p),pushup(q);
}
}T1;
int main(){
// freopen("123.txt","r",stdin);
in(m),in(T);
for(Re i=1;i<=m;++i)in(A[i]);
T1.build(pt[n=1],1,m);
while(T--){
in(op),in(p);
if(op<1)in(x),in(y),T1.split(pt[++n],pt[p],1,m,x,y);
else if(op<2)in(x),pt[p]=T1.merge(pt[p],pt[x],1,m),pt[x]=0;
else if(op<3)in(x),in(y),T1.change(pt[p],1,m,y,x);
else if(op<4)in(x),in(y),printf("%lld\n",T1.ask(pt[p],1,m,x,y));
else scanf("%lld",&K),printf("%d\n",T1.ask(pt[p],1,m,K));
}
}
#include<algorithm>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,logN=17;
int n,m,x,o,T,op,b[N],A[N],Ans[N],head[N];
struct QAQ{int to,next;}a[N];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
int pt[N];
struct Segment_Tree{
#define pl (tr[p].lp)
#define pr (tr[p].rp)
#define mid ((L+R)>>1)
int O;
struct QAQ{int lp,rp,S;}tr[N*(logN+1)];
inline void pushup(Re p){tr[p].S=tr[pl].S+tr[pr].S;}
inline void change(Re &p,Re L,Re R,Re x){
p=++O,++tr[p].S;
if(L==R)return;
if(x<=mid)change(pl,L,mid,x);
else change(pr,mid+1,R,x);
}
inline int merge(Re p,Re q,Re L,Re R){
if(!p||!q)return p+q;
if(L==R){tr[p].S+=tr[q].S;return p;}
pl=merge(pl,tr[q].lp,L,mid);
pr=merge(pr,tr[q].rp,mid+1,R);
pushup(p);return p;
}
inline int ask(Re &p,Re L,Re R,Re l,Re r){
if(!p)return 0;
if(l<=L&&R<=r)return tr[p].S;
Re ans=0;
if(l<=mid)ans+=ask(pl,L,mid,l,r);
if(r>mid)ans+=ask(pr,mid+1,R,l,r);
return ans;
}
}TR;
inline void dfs(Re x,Re fa){
TR.change(pt[x],1,m,A[x]);
for(Re i=head[x],to;i;i=a[i].next)
dfs(to=a[i].to,x),pt[x]=TR.merge(pt[x],pt[to],1,m);
if(A[x]<m)Ans[x]=TR.ask(pt[x],1,m,A[x]+1,m);
}
int main(){
in(n);
for(Re i=1;i<=n;++i)in(A[i]),b[i]=A[i];
sort(b+1,b+n+1),m=unique(b+1,b+n+1)-b-1;
for(Re i=1;i<=n;++i)A[i]=lower_bound(b+1,b+m+1,A[i])-b;
for(Re i=2;i<=n;++i)in(x),add(x,i);
dfs(1,0);
for(Re i=1;i<=n;++i)printf("%d\n",Ans[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LD double
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,M=5e4;
int n,x,T;LD b[N],k[N];char s[20];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline LD y(Re id,Re x){return k[id]*x+b[id];}
struct Segment_Tree{
#define pl (p<<1)
#define pr (p<<1|1)
#define mid ((L+R)>>1)
int tr[N<<2];
inline void change(Re p,Re L,Re R,Re id){
if(y(id,L)>y(tr[p],L)&&y(id,R)>y(tr[p],R)){tr[p]=id;return;}
if(y(id,L)<=y(tr[p],L)&&y(id,R)<=y(tr[p],R))return;
// if(L==R){if(y(id,L)>y(tr[p],L))tr[p]=id;return;}
if(k[tr[p]]<k[id]){
if(y(id,mid+1)>y(tr[p],mid+1))change(pl,L,mid,tr[p]),tr[p]=id;
else change(pr,mid+1,R,id);
}
else{
if(y(id,mid)>y(tr[p],mid))change(pr,mid+1,R,tr[p]),tr[p]=id;
else change(pl,L,mid,id);
}
}
inline LD ask(Re p,Re L,Re R,Re x){
if(L==R)return y(tr[p],x);
LD ans=y(tr[p],x);
if(x<=mid)return max(ans,ask(pl,L,mid,x));
else return max(ans,ask(pr,mid+1,R,x));
}
}TR;
int main(){
// freopen("123.txt","r",stdin);
in(T);
while(T--){
scanf("%s",s);
if(s[0]=='P')++n,scanf("%lf%lf",&b[n],&k[n]),TR.change(1,1,M,n);
else in(x),printf("%d\n",(int)(TR.ask(1,1,M,x-1)/100));
}
}
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstring>
#include<cstdio>
#define mid (L+R>>1)
#define Re register int
#define pl tree[p].lp
#define pr tree[p].rp
#define F(i,a,b) for(Re i=a;i<=b;++i)
#define lo(o) lower_bound(b+1,b+m+1,o)-b
using namespace std;
const int N=1e5+3,inf=2147483647;
int x,y,z,n,m,T,t,fu,cnt,tl,tr,a[N],b[N],pt[N],C[N],opt[N],ptl[20],ptr[20];
struct QAQ{int g,lp,rp;}tree[N*250];
struct O_O{int l,r,k;}Q[N];
struct T_T{int i,x;}c[N];
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline int ask_kth(Re L,Re R,Re k){
if(L==R)return b[R];
Re tmp=0;
F(i,1,tl)tmp-=tree[tree[ptl[i]].lp].g;
F(i,1,tr)tmp+=tree[tree[ptr[i]].lp].g;
if(tmp>=k){
F(i,1,tl)ptl[i]=tree[ptl[i]].lp;
F(i,1,tr)ptr[i]=tree[ptr[i]].lp;
return ask_kth(L,mid,k);
}
else{
F(i,1,tl)ptl[i]=tree[ptl[i]].rp;
F(i,1,tr)ptr[i]=tree[ptr[i]].rp;
return ask_kth(mid+1,R,k-tmp);
}
}
inline int ask_kth_pre(Re L,Re R,Re k){
tl=tr=0;
for(Re i=L-1;i;i-=i&-i)ptl[++tl]=pt[i];
for(Re i=R;i;i-=i&-i)ptr[++tr]=pt[i];
return ask_kth(1,m,k);
}
inline void add(Re &p,Re L,Re R,Re w,Re v){
if(!p)p=++cnt;tree[p].g+=v;
if(L==R)return;
if(w<=mid)add(pl,L,mid,w,v);
else add(pr,mid+1,R,w,v);
}
inline void add_pre(Re x,Re v){
Re w=lo(a[x]);
for(Re i=x;i<=n;i+=i&-i)add(pt[i],1,m,w,v);
}
inline int ask_level(Re p,Re L,Re R,Re x){
if(L==R)return tree[p].g;
if(x<=mid)return ask_level(pl,L,mid,x);
else return tree[pl].g+ask_level(pr,mid+1,R,x);
}
inline int ask_level_pre(Re L,Re R,Re w){
Re ans=0;
for(Re i=R;i;i-=i&-i)ans+=ask_level(pt[i],1,m,w);
for(Re i=L-1;i;i-=i&-i)ans-=ask_level(pt[i],1,m,w);
return ans;
}
int main(){
// printf("%lf\n",(sizeof(tree))/1024.0/1024.0);
// printf("%lf\n",(sizeof(tree)+sizeof(Q)+sizeof(c)+sizeof(a)+sizeof(b)+sizeof(pt)+sizeof(C))/1024.0/1024.0);
in(n),in(T),m=n;
F(i,1,n)in(a[i]),b[i]=a[i];
F(i,1,T){
in(opt[i]);
if(opt[i]==3)in(c[i].i),in(c[i].x),b[++m]=c[i].x;
else{
in(Q[i].l),in(Q[i].r),in(Q[i].k);
if(opt[i]!=2)b[++m]=Q[i].k;
}
}
sort(b+1,b+m+1);
m=unique(b+1,b+m+1)-b-1;
F(i,1,n)add_pre(i,1);
F(i,1,T){
if(opt[i]==1)
Q[i].k=lo(Q[i].k),
printf("%d\n",ask_level_pre(Q[i].l,Q[i].r,Q[i].k-1)+1);
if(opt[i]==2)
printf("%d\n",ask_kth_pre(Q[i].l,Q[i].r,Q[i].k));
if(opt[i]==3)
add_pre(c[i].i,-1),a[c[i].i]=c[i].x,add_pre(c[i].i,1);
if(opt[i]==4){
}
if(opt[i]==5){
}
}
}
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstring>
#include<cstdio>
#define mid (L+R>>1)
#define Re register int
#define pl tree[p].lp
#define pr tree[p].rp
#define F(i,a,b) for(Re i=a;i<=b;++i)
#define lo(o) lower_bound(b+1,b+m+1,o)-b
using namespace std;
const int N=1e5+3,inf=2147483647;
int x,y,z,n,m,T,t,fu,cnt,tl,tr,a[N],b[N],pt[N],C[N],opt[N],ptl[20],ptr[20];
struct QAQ{int g,lp,rp;}tree[N*250];
struct O_O{int l,r,k;}Q[N];
struct T_T{int i,x;}c[N];
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline int ask_kth(Re L,Re R,Re k){
if(L==R)return b[R];
Re tmp=0;
F(i,1,tl)tmp-=tree[tree[ptl[i]].lp].g;
F(i,1,tr)tmp+=tree[tree[ptr[i]].lp].g;
if(tmp>=k){
F(i,1,tl)ptl[i]=tree[ptl[i]].lp;
F(i,1,tr)ptr[i]=tree[ptr[i]].lp;
return ask_kth(L,mid,k);
}
else{
F(i,1,tl)ptl[i]=tree[ptl[i]].rp;
F(i,1,tr)ptr[i]=tree[ptr[i]].rp;
return ask_kth(mid+1,R,k-tmp);
}
}
inline int ask_kth_pre(Re L,Re R,Re k){
tl=tr=0;
for(Re i=L-1;i;i-=i&-i)ptl[++tl]=pt[i];
for(Re i=R;i;i-=i&-i)ptr[++tr]=pt[i];
return ask_kth(1,m,k);
}
inline void add(Re &p,Re L,Re R,Re w,Re v){
if(!p)p=++cnt;tree[p].g+=v;
if(L==R)return;
if(w<=mid)add(pl,L,mid,w,v);
else add(pr,mid+1,R,w,v);
}
inline void add_pre(Re x,Re v){
Re w=lo(a[x]);
for(Re i=x;i<=n;i+=i&-i)add(pt[i],1,m,w,v);
}
inline int ask_level(Re p,Re L,Re R,Re x){
if(L==R)return tree[p].g;
if(x<=mid)return ask_level(pl,L,mid,x);
else return tree[pl].g+ask_level(pr,mid+1,R,x);
}
inline int ask_level_pre(Re L,Re R,Re w){
Re ans=0;
for(Re i=R;i;i-=i&-i)ans+=ask_level(pt[i],1,m,w);
for(Re i=L-1;i;i-=i&-i)ans-=ask_level(pt[i],1,m,w);
return ans;
}
int main(){
in(n),in(T),m=n;
F(i,1,n)in(a[i]),b[i]=a[i];
F(i,1,T){
in(opt[i]);
if(opt[i]==3)in(c[i].i),in(c[i].x),b[++m]=c[i].x;
else{
in(Q[i].l),in(Q[i].r),in(Q[i].k);
if(opt[i]!=2)b[++m]=Q[i].k;
}
}
sort(b+1,b+m+1),m=unique(b+1,b+m+1)-b-1;
F(i,1,n)add_pre(i,1);
F(i,1,T){
if(opt[i]==1)Q[i].k=lo(Q[i].k),printf("%d\n",ask_level_pre(Q[i].l,Q[i].r,Q[i].k-1)+1);
if(opt[i]==2)printf("%d\n",ask_kth_pre(Q[i].l,Q[i].r,Q[i].k));
if(opt[i]==3)add_pre(c[i].i,-1),a[c[i].i]=c[i].x,add_pre(c[i].i,1);
if(opt[i]==4){
Re level=ask_level_pre(Q[i].l,Q[i].r,lo(Q[i].k)-1);
if(!level)printf("%d\n",-inf);
else printf("%d\n",ask_kth_pre(Q[i].l,Q[i].r,level));
}
if(opt[i]==5){
Re level=ask_level_pre(Q[i].l,Q[i].r,lo(Q[i].k));
if(level==Q[i].r-Q[i].l+1)printf("%d\n",inf);
else printf("%d\n",ask_kth_pre(Q[i].l,Q[i].r,level+1));
}
}
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=3e5+3,P=998244353;
int n,m,x,ans,inv1e4,f[N],b[N],p[N],A[N],fa[N],ch[N][3];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline int mi(Re x,Re k){
Re s=1;
while(k){
if(k&1)s=(LL)s*x%P;
x=(LL)x*x%P,k>>=1;
}
return s;
}
inline int inv(Re x){return mi(x,P-2);}
int pt[N];
struct Segment_Tree{
#define pl tr[p].lp
#define pr tr[p].rp
#define mid ((L+R)>>1)
int O;
struct QAQ{int S,lp,rp,mul;}tr[N*19];
inline void pushup(Re p){
tr[p].S=(tr[pl].S+tr[pr].S)%P;
}
inline void updata(Re p,Re v){
tr[p].S=(LL)tr[p].S*v%P,tr[p].mul=(LL)tr[p].mul*v%P;
}
inline void pushdown(Re p){
if(tr[p].mul!=1)updata(pl,tr[p].mul),updata(pr,tr[p].mul),tr[p].mul=1;
}
inline void change(Re &p,Re L,Re R,Re x,Re v){
if(!p)p=++O;tr[p].mul=1;
if(L==R){tr[p].S=v;return;}
pushdown(p);
if(x<=mid)change(pl,L,mid,x,v);
else change(pr,mid+1,R,x,v);
pushup(p);
}
inline int merge(Re p,Re q,Re pv,Re qv,Re v){
// printf("pv=%d, qv=%d, v=%d\n",pv,qv,v);
if(!p&&!q)return 0;
if(!p){updata(q,qv);return q;}
if(!q){updata(p,pv);return p;}
pushdown(p),pushdown(q);
Re plS=tr[pl].S,prS=tr[pr].S,qlS=tr[tr[q].lp].S,qrS=tr[tr[q].rp].S;
// printf("p:%d,%d q:%d,%d\n",tr[pl].S,tr[pr].S,tr[tr[q].lp].S,tr[tr[q].rp].S);
pl=merge(pl,tr[q].lp,(pv+(1-v+P)%P*1ll*qrS%P)%P,(qv+(1-v+P)%P*1ll*prS%P)%P,v);
pr=merge(pr,tr[q].rp,(pv+(LL)v*qlS%P)%P,(qv+(LL)v*plS%P)%P,v);
pushup(p);
return p;
}
inline void dfs_(Re p,Re L,Re R){
if(!p)return;
if(L==R){f[L]=tr[p].S;return;}
pushdown(p),dfs_(pl,L,mid),dfs_(pr,mid+1,R);
}
inline int ask(Re p,Re L,Re R,Re x){
if(!p)return 0;
if(L==R)return tr[p].S;
pushdown(p);
if(x<=mid)return ask(pl,L,mid,x);
else return ask(pr,mid+1,R,x);
}
}T1;
inline void dfs(Re x){
if(!ch[x][0])T1.change(pt[x],1,m,A[x],1);
else{
// printf("x=%d:\n",x);
// for(Re i=1;i<=m;++i)printf("%d ",T1.ask(pt[x],1,m,i));puts("");
dfs(ch[x][1]);
if(ch[x][0]<2)pt[x]=pt[ch[x][1]];
else dfs(ch[x][2]),pt[x]=T1.merge(pt[ch[x][1]],pt[ch[x][2]],0,0,p[x]);
// printf("x=%d:\n",x);
// for(Re i=1;i<=m;++i)printf("%d ",T1.ask(pt[x],1,m,i));puts("");
}
}
int main(){
// freopen("123.txt","r",stdin);
in(n),inv1e4=inv(10000);
for(Re i=1;i<=n;++i)in(fa[i]),ch[fa[i]][++ch[fa[i]][0]]=i;
for(Re i=1;i<=n;++i)
if(ch[i][0])in(p[i]),p[i]=(LL)p[i]*inv1e4%P;
else in(x),b[++m]=A[i]=x;
sort(b+1,b+m+1);
for(Re i=1;i<=n;++i)if(!ch[i][0])A[i]=lower_bound(b+1,b+m+1,A[i])-b;
// for(Re i=1;i<=n;++i)if(!ch[i][0])printf("%d: %d\n",i,A[i]);
dfs(1),T1.dfs_(1,1,m);
// for(Re i=1;i<=m;++i)printf("%d ",f[i]);puts("");
for(Re i=1;i<=m;++i)(ans+=(LL)i*b[i]%P*f[i]%P*f[i]%P)%=P;
printf("%d\n",ans);
}
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstring>
#include<cstdio>
#define mid (L+R>>1)
#define Re register int
#define pl tree[p].lp
#define pr tree[p].rp
#define F(i,a,b) for(Re i=a;i<=b;++i)
#define lo(o) lower_bound(b+1,b+m+1,o)-b
using namespace std;
const int N=1e5+3,inf=2147483647;
int m,T,t,fu,cnt,root,a[N],b[N],Q[N],opt[N];
struct QAQ{int g,lp,rp;}tree[N<<1];
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline int ask_kth(Re p,Re L,Re R,Re k){
if(L==R)return b[R];
Re tmp=tree[pl].g;
if(tmp>=k)return ask_kth(pl,L,mid,k);
else return ask_kth(pr,mid+1,R,k-tmp);
}
inline void add(Re &p,Re L,Re R,Re w,Re v){
if(!p)p=++cnt;tree[p].g+=v;
if(L==R)return;
if(w<=mid)add(pl,L,mid,w,v);
else add(pr,mid+1,R,w,v);
}
inline int ask_level(Re p,Re L,Re R,Re x){
if(!x)return 0;
if(L==R)return tree[p].g;
if(x<=mid)return ask_level(pl,L,mid,x);
else return tree[pl].g+ask_level(pr,mid+1,R,x);
}
int main(){
in(T);
F(i,1,T){
in(opt[i]),in(Q[i]);
if(opt[i]!=4)b[++m]=Q[i];
}
sort(b+1,b+m+1),m=unique(b+1,b+m+1)-b-1;
F(i,1,T){
if(opt[i]==1)add(root,1,m,lo(Q[i]),1);
if(opt[i]==2)add(root,1,m,lo(Q[i]),-1);
if(opt[i]==3)printf("%d\n",ask_level(root,1,m,lo(Q[i])-1)+1);
if(opt[i]==4)printf("%d\n",ask_kth(root,1,m,Q[i]));
if(opt[i]==5){
Re level=ask_level(root,1,m,lo(Q[i])-1);
printf("%d\n",ask_kth(root,1,m,level));
}
if(opt[i]==6){
Re level=ask_level(root,1,m,lo(Q[i]));
printf("%d\n",ask_kth(root,1,m,level+1));
}
}
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<stack>
#include<map>
#define LL long long
#define Re register int
#define mp make_pair
using namespace std;
const int N=2e5+3,logN=30;
int x,y,n,m,T,op,X[N],Y[N],OP[N];LL Ans[N];map<pair<int,int>,int>last,z;
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Union{// 冰茶姬(并查集)
struct BK{int x,y,dx,dy,sx,sy;BK(Re X=0,Re d1=0,Re S1=0,Re Y=0,Re d2=0,Re S2=0){x=X,y=Y,sx=S1,sy=S2,dx=d1,dy=d2;}};
int fa[N],dis[N],size[N];stack<BK>Q;
inline int find(Re x){return fa[x]==x?x:find(fa[x]);}
inline int Dis(Re x){return fa[x]==x?0:dis[x]^Dis(fa[x]);}
inline void merge(Re x,Re y,Re w){// 启发式合并
if(size[x]>size[y])swap(x,y);
Q.push(BK(x,dis[x],size[x],y,dis[y],size[y]));
fa[x]=y,dis[x]=w,size[y]+=size[x];
}
inline void back(Re to){// 撤销操作
while(int(Q.size())>to){
BK a=Q.top();Re x=a.x,y=a.y;Q.pop();
fa[x]=x,dis[x]=a.dx,size[x]=a.sx;
fa[y]=y,dis[y]=a.dy,size[y]=a.sy;
}
}
}TF;
struct Line_JI{
int p[31];stack<int>Q;
inline void insert(Re x){
for(Re i=logN;i>=0;--i)
if((x>>i)&1){
if(!p[i]){p[i]=x,Q.push(i);break;}
x^=p[i];
}
}
inline int ask(Re x){for(Re i=logN;i>=0;--i)if(p[i])x=min(x,x^p[i]);return x;}
inline void back(Re to){
while(int(Q.size())>to)p[Q.top()]=0,Q.pop();
}
}JI;
int o,head[N<<2];
struct QAQ{int x,y,w,next;}a[N*50];
inline void add(Re x,Re y1,Re y2,Re w){a[++o].w=w,a[o].x=y1,a[o].y=y2,a[o].next=head[x],head[x]=o;}
struct Segment_Tree{
#define pl (p<<1)
#define pr (p<<1|1)
#define mid ((L+R)>>1)
inline void change(Re p,Re L,Re R,Re l,Re r,Re x,Re y,Re v){
if(l>r)return;
if(l<=L&&R<=r){add(p,x,y,v);return;}
if(l<=mid)change(pl,L,mid,l,r,x,y,v);
if(r>mid)change(pr,mid+1,R,l,r,x,y,v);
}
inline void dfs(Re p,Re L,Re R){
Re tmp1=TF.Q.size(),tmp2=JI.Q.size();
for(Re i=head[p];i;i=a[i].next){
Re x=TF.find(a[i].x),y=TF.find(a[i].y),w=TF.Dis(a[i].x)^TF.Dis(a[i].y)^a[i].w;
if(x!=y)TF.merge(x,y,w);
else JI.insert(w);
}
if(L==R){if(OP[L])Ans[L]=JI.ask(TF.Dis(X[L])^TF.Dis(Y[L]));}
else dfs(pl,L,mid),dfs(pr,mid+1,R);
TF.back(tmp1),JI.back(tmp2);
}
}T1;
int main(){
// freopen("123.txt","r",stdin);
in(n),in(m);
for(Re i=1;i<=n;++i)TF.fa[i]=i,TF.size[i]=1;
for(Re i=1;i<=m;++i){
in(x),in(y);if(x>y)swap(x,y);
in(z[mp(x,y)]),last[mp(x,y)]=1;
}
in(T);
for(Re i=1;i<=T;++i){
in(op),in(x),in(y);if(x>y)swap(x,y);
if(op<2)in(z[mp(x,y)]),last[mp(x,y)]=i;
else if(op<3)T1.change(1,1,T,last[mp(x,y)],i-1,x,y,z[mp(x,y)]),last.erase(last.find(mp(x,y)));
else OP[i]=1,X[i]=x,Y[i]=y;
}
for(map<pair<int,int>,int>::iterator it=last.begin();it!=last.end();++it)
T1.change(1,1,T,it->second,T,it->first.first,it->first.second,z[it->first]);
T1.dfs(1,1,T);
for(Re i=1;i<=T;++i)if(OP[i])printf("%lld\n",Ans[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,logN=18;
int n,x,y,z,w,op,m1,m2,T,A[N],t1[N],t2[N],Ans[N];
struct Change{int i,v,t;inline bool operator<(const Change &O)const{return i<O.i;}}C[N],tmp[N];
struct Query{int x,l,r,id;}Q[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
int pt[N];
struct Trie{
int O,cnt[N*(logN+2)],tr[N*(logN+2)][2];
inline void insert(Re p,Re q,Re o,Re x){
if(o<0)return;Re i=(x>>o)&1;
tr[p][i]=++O,tr[p][i^1]=tr[q][i^1];
cnt[tr[p][i]]=cnt[tr[q][i]]+1;
insert(tr[p][i],tr[q][i],o-1,x);
}
inline int ask(Re p,Re q,Re o,Re x){
if(o<0)return 0;Re i=(x>>o)&1;
if(cnt[tr[q][i^1]]>cnt[tr[p][i^1]])return (1<<o)+ask(tr[p][i^1],tr[q][i^1],o-1,x);
else return ask(tr[p][i],tr[q][i],o-1,x);
}
}T1;
struct Segment_Tree{
#define pl (p<<1)
#define pr (p<<1|1)
#define mid ((L+R)>>1)
vector<Query>tr[N<<2];
inline void change(Re p,Re L,Re R,Re l,Re r,Query &v){
if(l>r)return;
if(l<=L&&R<=r){tr[p].push_back(v);return;}
if(l<=mid)change(pl,L,mid,l,r,v);
if(r>mid)change(pr,mid+1,R,l,r,v);
}
inline int find1(Re l,Re r,Re id){
if(C[r].i<id)return r+1;
while(l<r){
Re Mid=l+r>>1;
if(C[Mid].i>=id)r=Mid;
else l=Mid+1;
}
return r;
}
inline int find2(Re l,Re r,Re id){
if(C[r].i<=id)return r+1;
while(l<r){
Re Mid=l+r>>1;
if(C[Mid].i>id)r=Mid;
else l=Mid+1;
}
return r;
}
inline void CDQ(Re p,Re L,Re R,Re l,Re r){
if(l>r)return;
T1.O=pt[l-1]=0;
for(Re i=l;i<=r;++i)T1.insert(pt[i]=++T1.O,pt[i-1],logN,C[i].v);
for(vector<Query>::iterator it=tr[p].begin();it!=tr[p].end();++it){
Re ll=find1(l,r,it->l)-1,rr=find2(l,r,it->r)-1;
if(ll<rr)Ans[it->id]=max(Ans[it->id],T1.ask(pt[ll],pt[rr],logN,it->x));
}
if(L==R)return;
Re p1=l-1;for(Re i=l;i<=r;++i)if(C[i].t<=mid)tmp[++p1]=C[i];
Re p2=p1;for(Re i=l;i<=r;++i)if(C[i].t>mid)tmp[++p2]=C[i];
for(Re i=l;i<=r;++i)C[i]=tmp[i];
CDQ(pl,L,mid,l,p1),CDQ(pr,mid+1,R,p1+1,r);
}
}TR;
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T);
for(Re i=1;i<=n;++i)in(A[i]),T1.insert(pt[i]=++T1.O,pt[i-1],logN,A[i]);
for(Re i=1;i<=T;++i){
in(op),in(x),in(y);
if(!op)++m1,C[m1]=(Change){x,y,m1};
else in(z),in(w),++m2,Q[m2]=(Query){z,x,y,m2},t1[m2]=max(1,m1-w+1),t2[m2]=m1;
}
for(Re i=1;i<=m2;++i)Ans[i]=T1.ask(pt[Q[i].l-1],pt[Q[i].r],logN,Q[i].x),TR.change(1,1,m1,t1[i],t2[i],Q[i]);
sort(C+1,C+m1+1),TR.CDQ(1,1,m1,1,m1);
for(Re i=1;i<=m2;++i)printf("%d\n",Ans[i]);
}