模板代码复习

#include<bits/stdc++.h>
#define MAXN 100010
using namespace std;
int n,m,ind[MAXN],head[MAXN];
stack<int> stk;
vector<int> G[MAXN];
inline void addedge(int from,int to){
	G[from].push_back(to);
	++ind[to];
}
inline void dfs(int from){
	for(int &i=head[from];i<G[from].size();){
		dfs(G[from][i++]);
	}
	stk.push(from);
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;++i){
		int from,to;
		scanf("%d %d",&from,&to);
		addedge(from,to);
	}
	int start=0;
	for(int i=1;i<=n;++i){
		sort(G[i].begin(),G[i].end());
		if(abs(int(G[i].size())-ind[i])>1){
			puts("No");
			return 0;
		}
		if(G[i].size()>ind[i]){
			if(start){
				puts("No");
				return 0;
			}else{
				start=i;
			}
		}
	}
	start=start?start:1;
	dfs(start);
	if(stk.size()!=m+1){
		puts("No");
		return 0;
	}
	while(!stk.empty()){
		printf("%d ",stk.top());
		stk.pop();
	} 
	return 0;
}

#include<bits/stdc++.h>
#define MAXN 110
using namespace std;
typedef long long ll;
int n,m,G[MAXN][MAXN];
ll dis[MAXN][MAXN];
int main(){
	scanf("%d %d",&n,&m);
	memset(G,0x3f,sizeof(G));
	memset(dis,0x3f,sizeof(dis));
	for(int i=1;i<=m;++i){
		int u,v,w;
		scanf("%d %d %d",&u,&v,&w);
		dis[u][v]=dis[v][u]=min(dis[u][v],1ll*w);
	}
	for(int i=1;i<=n;++i){
		dis[i][i]=0;
	}
	for(int k=1;k<=n;++k){
		for(int i=1;i<=n;++i){
			for(int j=1;j<=n;++j){
				if(i==j||j==k||k==i){
					continue;
				}
				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
			}
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			printf("%lld ",dis[i][j]);
		}
		putchar('\n');
	}
	return 0;
}

#include<bits/stdc++.h>
#define MAXN 100001
#define MAXM 200002
using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;
struct node{
	int to,next;
	ll dis;
}edge[MAXM];
int n,m,s,cnt,head[MAXN];
ll dis[MAXN];
bool vis[MAXN];
inline void addedge(int from,int to,ll dis){
	edge[++cnt].to=to;
	edge[cnt].next=head[from];
	edge[cnt].dis=dis;
	head[from]=cnt;
}
inline void Dijiestra(){
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f,sizeof(dis));
	vis[s]=true;
	dis[s]=0;
	priority_queue<pli,vector<pli>,greater<pli> > q;
	q.push(make_pair(0,s));
	while(!q.empty()){
		int from=q.top().second;
		q.pop();
		vis[from]=false;
		for(int i=head[from];i;i=edge[i].next){
			int to=edge[i].to;
			if(dis[to]>dis[from]+edge[i].dis){
				dis[to]=dis[from]+edge[i].dis;
				if(!vis[to]){
					q.push(make_pair(dis[to],to));
					vis[to]=true;
				}
			}
		}
	}
} 
int main(){
	scanf("%d %d %d",&n,&m,&s);
	while(m--){
		int from,to;
		ll dis;
		scanf("%d %d %lld",&from,&to,&dis);
		addedge(from,to,dis);
	}
	Dijiestra();
	for(int i=1;i<=n;++i){
		printf("%lld ",dis[i]);
	}
	return 0;
}

#include<bits/stdc++.h>
#define MAXN 100001
#define MAXM 200002
using namespace std;
typedef long long ll;
struct node{
	int to,nxt;
	ll dis;
}edge[MAXM];
int n,m,s,cnt,head[MAXN],pos[MAXN<<2];
bool vis[MAXN];
ll dis[MAXN],ans[MAXN],tree[MAXN<<2];
inline void addedge(int from,int to,ll dis){
	edge[++cnt].to=to;
	edge[cnt].dis=dis;
	edge[cnt].nxt=head[from];
	head[from]=cnt;
} 
inline void push_up(int root){
	if(tree[root<<1]<tree[root<<1|1]){
		tree[root]=tree[root<<1];
		pos[root]=pos[root<<1];
	}else{
		tree[root]=tree[root<<1|1];
		pos[root]=pos[root<<1|1];
	}
}
void build(int root,int l,int r){
	if(l==r){
		tree[root]=INT_MAX;
		pos[root]=l;
		return;
	}
	int mid=(l+r)>>1;
	build(root<<1,l,mid);
	build(root<<1|1,mid+1,r);
	push_up(root); 
}
void change(int root,int pos,ll k,int l,int r){
	if(l==pos&&r==pos){
		tree[root]=k;
		return;
	}
	int mid=(l+r)>>1;
	if(pos<=mid){
		change(root<<1,pos,k,l,mid); 
	}else{
		change(root<<1|1,pos,k,mid+1,r);
	}
	push_up(root);
}
inline void Dijiestra(int s){
	fill(dis+1,dis+n+1,INT_MAX);
	build(1,1,n);
	dis[s]=0ll;
	for(int i=1;i<=n;++i){
		ans[s]=dis[s];
		ll disu=dis[s];
		change(1,s,ll(INT_MAX)+1ll,1,n);
		for(int j=head[s];j;j=edge[j].nxt){
			int to=edge[j].to;
			if(dis[to]<=INT_MAX&&dis[to]>dis[s]+edge[j].dis){
				dis[to]=dis[s]+edge[j].dis;
				change(1,to,dis[to],1,n);
			}
		}
		s=pos[1];
	}
}
int main(){
	scanf("%d %d %d",&n,&m,&s);
	while(m--){
		int x,y;
		ll dis;
		scanf("%d %d %lld",&x,&y,&dis);
		addedge(x,y,dis);
	}
	Dijiestra(s);
	for(int i=1;i<=n;++i){
		printf("%lld ",ans[i]);
	}
	return 0;
}

#include<algorithm>
#include<iostream>
using namespace std;
struct node{
	int first,second,dist;
	operator int(){
		return dist;
	};
};
node graph[200002];
int maxn,maxm;
int father[5005];
inline int get(int son){
	if(son==father[son]){
		return son;
	};
	return father[son]=get(father[son]);
};
inline void merge(int first,int second){
	father[get(first)]=get(second);
};
int main(int argc,char **argv){
	ios::sync_with_stdio(false);
	cin>>maxn>>maxm;
	for(int iter=1;iter<=maxm;++iter){
		cin>>graph[iter].first>>graph[iter].second>>graph[iter].dist;
	};
	for(int iter=1;iter<=maxn;++iter){
		father[iter]=iter;
	};
	sort(graph+1,graph+maxm+1);
	int answer=0,choise=0;
	for(int iter=1;iter<=maxm;++iter){
		int first=graph[iter].first;
		int second=graph[iter].second;
		if(get(first)!=get(second)){
			answer+=graph[iter].dist;
			merge(first,second);
			++choise;
		};
	};
	if(choise!=maxn-1){
		cout<<"orz";
		return 0;
	};
	cout<<answer;
};

#include<bits/stdc++.h>
#define MAXN 500005
using namespace std;
struct node{
	int to,next;
}edge[MAXN<<1];
int n,m,cnt,root,head[MAXN],dep[MAXN],fa[MAXN][26]; 
inline void addedge(int from,int to){
	edge[++cnt].to=to;
	edge[cnt].next=head[from];
	head[from]=cnt;
}
void dfs(int from,int pa){
	dep[from]=dep[pa]+1;
	fa[from][0]=pa;
	for(int i=1;i<=25;++i){
		fa[from][i]=fa[fa[from][i-1]][i-1];
	}
	for(int i=head[from];i;i=edge[i].next){
		int to=edge[i].to;
		if(to==pa){
			continue;
		}
		dfs(to,from);
	}
}
inline int lca(int x,int y){
	if(dep[x]>dep[y]){
		swap(x,y);
	}
	for(int i=25;i>=0;--i){
		if(dep[fa[y][i]]>=dep[x]){
			y=fa[y][i];
		}
	}
	if(x==y){
		return x;
	}
	for(int i=25;i>=0;--i){
		if(fa[x][i]!=fa[y][i]){
			x=fa[x][i];
			y=fa[y][i];
		}
	}
	return fa[x][0];
}
int main(){
	scanf("%d %d %d",&n,&m,&root);
	for(int i=1;i<n;++i){
		int from,to;
		scanf("%d %d",&from,&to);
		addedge(from,to);
		addedge(to,from);
	}
	dfs(root,0);
	while(m--){
		int x,y;
		scanf("%d %d",&x,&y);
		printf("%d\n",lca(x,y));
	}
	return 0;
}

#include<bits/stdc++.h>
#define MAXN 500010
using namespace std;
struct node{
	int to,next;
	node(int to=0,int next=0){
		this->to=to;
		this->next=next; 
	}
}edge[MAXN<<1];
int n,m,cnt,tim,root,head[MAXN],dfn[MAXN],st[MAXN][26],logn[MAXN];
inline void addedge(int from,int to){
	edge[++cnt]=node(to,head[from]);
	head[from]=cnt;
}
inline void dfs(int from,int fa){
	dfn[from]=++tim;
	st[tim][0]=fa;
	for(int i=head[from];i;i=edge[i].next){
		int to=edge[i].to;
		if(to^fa){
			dfs(to,from);
		}
	}
}
inline int merge(int x,int y){
	return dfn[x]<dfn[y]?x:y;
}
inline void init(){
	dfs(root,0);
	for(int i=2;i<=n;++i){
		logn[i]=logn[i>>1]+1;
	}
	for(int i=1;i<=logn[n];++i){
		for(int j=1;j<=n-(1<<i)+1;++j){
			st[j][i]=merge(st[j][i-1],st[j+(1<<(i-1))][i-1]);
		}
	} 
}
inline int lca(int x,int y){
    if(x==y){
        return x;
    }
	x=dfn[x];
	y=dfn[y];
	if(x>=y){
		swap(x,y);
	}
	int k=logn[y-x];
	return merge(st[x+1][k],st[y-(1<<k)+1][k]);
}
int main(){
	scanf("%d %d %d",&n,&m,&root);
	for(int i=1;i<n;++i){
		int from,to;
		scanf("%d %d",&from,&to);
		addedge(from,to);
		addedge(to,from);
	}
	init();
	while(m--){
		int x,y;
		scanf("%d %d",&x,&y);
		printf("%d\n",lca(x,y));
	}
	return 0;
}

#include<bits/stdc++.h>
#define MAXN 100001
using namespace std;
struct Node{
	int to,next;
}edge[MAXN<<1];
struct Segement{
	int val,tag;
}tree[MAXN<<2];
int n,m,root,mod,a[MAXN],w[MAXN];
int cnt,tim,head[MAXN],fa[MAXN],dep[MAXN],siz[MAXN],dfn[MAXN],top[MAXN],son[MAXN];
inline void push_up(int root){
	tree[root].val=(tree[root<<1].val+tree[root<<1|1].val)%mod;
}
inline void update(Segement &dot,int l,int r,int tag){
	(dot.tag+=tag)%=mod;
	(dot.val+=1ll*(r-l+1)*tag%mod)%=mod;
}
inline int push_down(int root,int l,int r){
	int tag=tree[root].tag;
	int mid=(l+r)>>1;
	tree[root].tag=0;
	update(tree[root<<1],l,mid,tag);
	update(tree[root<<1|1],mid+1,r,tag);
	return mid;
}
void build(int root,int l,int r){
	if(l==r){
		tree[root].val=w[l]%mod;
		return;
	}
	int mid=(l+r)>>1;
	build(root<<1,l,mid);
	build(root<<1|1,mid+1,r);
	push_up(root);
}
void change(int root,int l,int r,int L,int R,int tag){
	if(L<=l&&r<=R){
		update(tree[root],l,r,tag);
		return;
	}
	int mid=push_down(root,l,r);
	if(L<=mid){
		change(root<<1,l,mid,L,R,tag);
	}
	if(mid<R){
		change(root<<1|1,mid+1,r,L,R,tag);
	}
	push_up(root);
}
int query(int root,int l,int r,int L,int R){
	if(L<=l&&r<=R){
		return tree[root].val;
	}
	int mid=push_down(root,l,r);
	int res=0;
	if(L<=mid){
		res+=query(root<<1,l,mid,L,R);
	}
	if(mid<R){
		(res+=query(root<<1|1,mid+1,r,L,R))%=mod;
	}
	return res;
}
inline void addedge(int from,int to){
	edge[++cnt].to=to;
	edge[cnt].next=head[from];
	head[from]=cnt;
}
void dfs1(int from,int pa){
	dep[from]=dep[pa]+1;
	fa[from]=pa;
	siz[from]=1;
	for(int i=head[from];i;i=edge[i].next){
		int to=edge[i].to;
		if(to==pa){
			continue;
		}
		dfs1(to,from);
		siz[from]+=siz[to];
		if(siz[to]>siz[son[from]]){
			son[from]=to;
		}
	}
}
void dfs2(int from,int topf){
	dfn[from]=++tim;
	w[tim]=a[from];
	top[from]=topf;
	if(!son[from]){
		return;
	}
	dfs2(son[from],topf);
	for(int i=head[from];i;i=edge[i].next){
		int to=edge[i].to;
		if(to==fa[from]||to==son[from]){
			continue;
		} 
		dfs2(to,to);
	}
}
inline void change_chain(int u,int v,int tag){
	tag%=mod;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]]){
			swap(u,v);
		}
		change(1,1,n,dfn[top[u]],dfn[u],tag);
		u=fa[top[u]];
	}
	if(dep[u]>dep[v]){
		swap(u,v);
	}
	change(1,1,n,dfn[u],dfn[v],tag);
}
inline int query_chain(int u,int v){
	int res=0;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]]){
			swap(u,v);
		}
		(res+=query(1,1,n,dfn[top[u]],dfn[u]))%=mod;
		u=fa[top[u]];
	}
	if(dep[u]>dep[v]){
		swap(u,v);
	}
	return (res+query(1,1,n,dfn[u],dfn[v]))%mod;
}
inline void change_tree(int root,int tag){
	tag%=mod;
	change(1,1,n,dfn[root],dfn[root]+siz[root]-1,tag);
}
inline int query_tree(int root){
	return query(1,1,n,dfn[root],dfn[root]+siz[root]-1);
}
int main(){
	scanf("%d %d %d %d",&n,&m,&root,&mod);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<n;++i){
		int from,to;
		scanf("%d %d",&from,&to);
		addedge(from,to);
		addedge(to,from);
	}
	dfs1(root,0);
	dfs2(root,root);
	build(1,1,n);
	while(m--){
		int opt,x,y,z;
		scanf("%d %d",&opt,&x);
		if(opt==1){
			scanf("%d %d",&y,&z);
			change_chain(x,y,z);
		}else if(opt==2){
			scanf("%d",&y);
			printf("%d\n",query_chain(x,y));
		}else if(opt==3){
			scanf("%d",&y);
			change_tree(x,y);
		}else{
			printf("%d\n",query_tree(x));
		}
	}
	return 0;
}

#include<bits/stdc++.h>
#define MAXN 100001
using namespace std;
int n,m,st[MAXN][26],logn[MAXN];
inline void prework(){
	for(int i=2;i<=n;++i){
		logn[i]=logn[i>>1]+1;
	}
	for(int i=1;(1<<i)<=n;++i){
		for(int j=1;j<=n-(1<<i)+1;++j){
			st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
		}
	}
}
inline int query(int l,int r){
	int k=logn[r-l+1];
	return max(st[l][k],st[r-(1<<k)+1][k]);
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&st[i][0]);
	}
	prework();
	while(m--){
		int l,r;
		scanf("%d %d",&l,&r);
		printf("%d\n",query(l,r));
	}
	return 0;
}

#include<bits/stdc++.h>
#define int long long
#define MAXN 100001
using namespace std;
struct node{
	int val,lazy;
}tree[MAXN<<2];
int n,m;
inline void push_up(int root){
	tree[root].val=tree[root<<1].val+tree[root<<1|1].val;
}
inline void push_down(const int root,const int l,const int r){
	const int lazy=tree[root].lazy;
	const int mid=(l+r)>>1;
	tree[root<<1].lazy+=lazy;
	tree[root<<1|1].lazy+=lazy;
	tree[root<<1].val+=(mid-l+1)*lazy;
	tree[root<<1|1].val+=(r-mid)*lazy;
	tree[root].lazy=0;
}
void build(int root,int l,int r){
	if(l==r){
		scanf("%lld",&tree[root].val);
		return;
	}
	const int mid=(l+r)>>1;
	build(root<<1,l,mid);
	build(root<<1|1,mid+1,r);
	push_up(root);
}
void change(int root,int l,int r,int L,int R,int tag){
	if(L<=l&&r<=R){
		tree[root].val+=(r-l+1)*tag;
		tree[root].lazy+=tag;
		return;
	}
	const int mid=(l+r)>>1;
	push_down(root,l,r);
	if(L<=mid){
		change(root<<1,l,mid,L,R,tag);
	}
	if(mid<R){
		change(root<<1|1,mid+1,r,L,R,tag);
	}
	push_up(root);
}
int query(int root,int l,int r,int L,int R){
	if(L<=l&&r<=R){
		return tree[root].val;
	}
	const int mid=(l+r)>>1;
	push_down(root,l,r);
	int res=0;
	if(L<=mid){
		res+=query(root<<1,l,mid,L,R);
	}
	if(mid<R){
		res+=query(root<<1|1,mid+1,r,L,R);
	}
	return res;
}
signed main(){
	scanf("%lld %lld",&n,&m);
	build(1,1,n);
	while(m--){
		int opt,l,r;
		scanf("%lld %lld %lld",&opt,&l,&r);
		if(opt==1){
			int tag;
			scanf("%lld",&tag);
			change(1,1,n,l,r,tag);
		}else{
			printf("%lld\n",query(1,1,n,l,r));
		}
	}
	return 0;
}

#include<bits/stdc++.h>
#define MAXN 500005
#define INF INT_MIN
using namespace std;
struct node{
	int l,r,sum,maxl,maxr,maxi;
	inline int maxp(){
		return max(maxi,max(maxl,maxr));
	}
}tree[MAXN<<2];
inline void merge(node &res,node x,node y){
	res.sum=x.sum+y.sum;
	res.maxl=max(x.maxl,x.sum+y.maxl);
	res.maxr=max(x.maxr+y.sum,y.maxr);
//	if(x.maxr<0&&y.maxl<0){
//		res.maxi=max(x.maxr,y.maxl);
//	}else{
//		if(x.maxr<0){
//			res.maxi+=x.maxr;
//		}
//		if(y.maxl<0){
//			res.maxi+=y.maxl;
//		}
//	}
//	res.maxi=max(res.maxi,max(x.maxi,y.maxi));
	res.maxi=max(x.maxr+y.maxl,max(x.maxi,y.maxi));
}
inline void pushup(int root){
	merge(tree[root],tree[root<<1],tree[root<<1|1]);
}
void build(int root,int l,int r){
	tree[root]=(node){l,r,0,INF,INF,INF};
	if(l==r){
		int val;
		scanf("%d",&val);
		tree[root]=(node){l,r,val,val,val,val};
		return;
	}
	int mid=(l+r)>>1;
	build(root<<1,l,mid);
	build(root<<1|1,mid+1,r);
	pushup(root);
}
void change(int root,int pos,int val){
	if(tree[root].l==tree[root].r){
		tree[root]=(node){tree[root].l,tree[root].r,val,val,val,val};
		return;
	}
	int mid=(tree[root].l+tree[root].r)>>1;
	if(pos<=mid){
		change(root<<1,pos,val);
	}else{
		change(root<<1|1,pos,val);
	}
	pushup(root);
}
node query(int root,int l,int r){
	if(l<=tree[root].l&&tree[root].r<=r){
		return tree[root];
	}
	int mid=(tree[root].l+tree[root].r)>>1;
	if(r<=mid){
		return query(root<<1,l,r);
	}else if(mid<l){
		return query(root<<1|1,l,r);
	}else{
		node res;
		merge(res,query(root<<1,l,r),query(root<<1|1,l,r));
		return res;
	}
}
int main(){
	int n,m;
	scanf("%d %d",&n,&m);
	build(1,1,n);
	while(m--){
		int opt;
		scanf("%d",&opt);
		if(opt==1){
			int l,r;
			scanf("%d %d",&l,&r);
			if(l>r){
				swap(l,r);
			}
			printf("%d\n",query(1,l,r).maxp());
		}else{
			int pos,k;
			scanf("%d %d",&pos,&k);
			change(1,pos,k);
		}
	}
	return 0;
}

#include<bits/stdc++.h>
#define MAXN 200010
#define MAXM 1000010
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#define Opt optimize
#define tar target
#pragma GCC Opt(3)
#pragma GCC tar("avx")
#pragma GCC Opt("Ofast")
#pragma GCC Opt("inline")
#pragma GCC Opt("-fgcse")
#pragma GCC Opt("-fgcse-lm")
#pragma GCC Opt("-fipa-sra")
#pragma GCC Opt("-ftree-pre")
#pragma GCC Opt("-ftree-vrp")
#pragma GCC Opt("-fpeephole2")
#pragma GCC Opt("-ffast-math")
#pragma GCC Opt("-fsched-spec")
#pragma GCC Opt("unroll-loops")
#pragma GCC Opt("-falign-jumps")
#pragma GCC Opt("-falign-loops")
#pragma GCC Opt("-falign-labels")
#pragma GCC Opt("-fdevirtualize")
#pragma GCC Opt("-fcaller-saves")
#pragma GCC Opt("-fcrossjumping")
#pragma GCC Opt("-fthread-jumps")
#pragma GCC Opt("-funroll-loops")
#pragma GCC Opt("-fwhole-program")
#pragma GCC Opt("-freorder-blocks")
#pragma GCC Opt("-fschedule-insns")
#pragma GCC Opt("inline-functions")
#pragma GCC Opt("-ftree-tail-merge")
#pragma GCC Opt("-fschedule-insns2")
#pragma GCC Opt("-fstrict-aliasing")
#pragma GCC Opt("-fstrict-overflow")
#pragma GCC Opt("-falign-functions")
#pragma GCC Opt("-fcse-skip-blocks")
#pragma GCC Opt("-fcse-follow-jumps")
#pragma GCC Opt("-fsched-interblock")
#pragma GCC Opt("-fpartial-inlining")
#pragma GCC Opt("no-stack-protector")
#pragma GCC Opt("-freorder-functions")
#pragma GCC Opt("-findirect-inlining")
#pragma GCC Opt("-fhoist-adjacent-loads")
#pragma GCC Opt("-frerun-cse-after-loop")
#pragma GCC Opt("inline-small-functions")
#pragma GCC Opt("-finline-small-functions")
#pragma GCC Opt("-ftree-switch-conversion")
#pragma GCC Opt("-foptimize-sibling-calls")
#pragma GCC Opt("-fexpensive-optimizations")
#pragma GCC Opt("-funsafe-loop-optimizations")
#pragma GCC Opt("inline-functions-called-once")
#pragma GCC Opt("-fdelete-null-pointer-checks")
#pragma GCC Opt(2)
using namespace std;
typedef long long ll;
struct node{
	ll val,tag;
}tree[MAXN<<2];
int n,a[MAXN],last[MAXM];
ll dp[MAXN];
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
inline int read(){
	register int res=0,f=1;
	register char c=getchar();
	while(!isdigit(c)){
		if(c=='-'){
			f=-1;
		}
		c=getchar();
	}
	while(isdigit(c)){
		res=(res<<1)+(res<<3)+(c^48);
		c=getchar();
	}
	return res*f;
}
inline void push_up(int root){
	tree[root].val=max(tree[root<<1].val,tree[root<<1|1].val);
}
inline int push_down(int root,int l,int r){
	int mid=(l+r)>>1;
	if(!tree[root].tag){
		return mid;
	}
	tree[root<<1].tag+=tree[root].tag;
	tree[root<<1].val+=tree[root].tag;
	tree[root<<1|1].tag+=tree[root].tag;
	tree[root<<1|1].val+=tree[root].tag;
	tree[root].tag=0;
	return mid;
} 
inline void build(int root,int l,int r){
	tree[root].tag=0;
	if(l==r){
		tree[root].val=0;
		return;
	}
	int mid=(l+r)>>1;
	build(root<<1,l,mid);
	build(root<<1|1,mid+1,r);
	push_up(root);
}
inline void change_max(int root,int l,int r,int pos,ll val){
	if(l==r){
		tree[root].val=max(tree[root].val,val);
		return;
	}
	int mid=push_down(root,l,r);
	if(pos<=mid){
		change_max(root<<1,l,mid,pos,val);
	}else{
		change_max(root<<1|1,mid+1,r,pos,val);
	}
	push_up(root);
}
inline void change_add(int root,int l,int r,int L,int R,ll val){
	if(L<=l&&r<=R){
		tree[root].val+=val;
		tree[root].tag+=val;
		return;
	} 
	int mid=push_down(root,l,r);
	if(L<=mid){
		change_add(root<<1,l,mid,L,R,val);
	}
	if(mid<R){
		change_add(root<<1|1,mid+1,r,L,R,val);
	}
	push_up(root);
}
inline ll query(int root,int l,int r,int L,int R){
	if(L<=l&&r<=R){
		return tree[root].val;
	}
	int mid=push_down(root,l,r);
	if(L>mid){
		return query(root<<1|1,mid+1,r,L,R);
	}
	if(mid>=R){
		return query(root<<1,l,mid,L,R);
	}
	return max(query(root<<1,l,mid,L,R),query(root<<1|1,mid+1,r,L,R));
}
inline void print(int root,int l,int r){
	if(l==r){
		printf("%lld ",tree[root].val);
		return;
	}
	int mid=push_down(root,l,r);
	print(root<<1,l,mid);
	print(root<<1|1,mid+1,r);
}
inline void solve(){
	const int n=read();
	register ll ans=0;
	fill(dp+1,dp+1+n,0);
	fill(last+1,last+MAXM,0);
	build(1,1,n);
	for(register int i=1;i<=n;++i){
		a[i]=read();
		if(i==1){
			last[a[1]]=1;
			continue;
		}
		change_add(1,1,n,i-1,i-1,(a[i]==a[i-1])*a[i]);
		if(i>2){
			change_max(1,1,n,i-1,query(1,1,n,1,i-2));
			if(last[a[i]]&&last[a[i]]!=i-1){
				change_max(1,1,n,i-1,query(1,1,n,last[a[i]],last[a[i]])+a[i]);
			}
			change_add(1,1,n,1,i-2,(a[i]==a[i-1])*a[i]);
		}
		
		last[a[i]]=i;
	}
	printf("%lld\n",query(1,1,n,1,n-1));
}
int main(){
	register int T=read();
	while(T--){
		solve();
	}
	return 0;
}

#include<bits/stdc++.h>
#define MAXN 10001
using namespace std;
int fa[MAXN];
inline int get(int x){
	if(fa[x]==x){
		return x;
	}
	return fa[x]=get(fa[x]);
}
inline void merge(int x,int y){
	fa[get(x)]=get(y);
}
int main(){
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;++i){
		fa[i]=i;
	}
	while(m--){
		int opt,x,y;
		scanf("%d %d %d",&opt,&x,&y);
		if(opt==1){
			merge(x,y);
		}else{
			if(get(x)==get(y)){
				puts("Y");
			}else{
				puts("N");
			}
		}
	}
	return 0;
}

#include<bits/stdc++.h>
#define MAXN 100001
using namespace std;
struct node{
	int lson,rson,val,randkey,size;
}tree[MAXN];
int n,cnt,root;
inline void pushup(const int root){
	tree[root].size=tree[tree[root].lson].size+tree[tree[root].rson].size+1;
}
inline int newnode(const int val){
	tree[++cnt].val=val;
	tree[cnt].size=1;
	tree[cnt].randkey=rand();
	return cnt;
}
inline void split(const int root,const int val,int &x,int &y){
	if(!root){
		x=y=0;
		return;
	}
	if(tree[root].val<=val){
		x=root;
		split(tree[root].rson,val,tree[root].rson,y);
	}else{
		y=root;
		split(tree[root].lson,val,x,tree[root].lson);
	}
	pushup(root);
}
inline int merge(const int x,const int y){
	if(!x||!y){
		return x+y;
	}
	if(tree[x].randkey<tree[y].randkey){
		tree[x].rson=merge(tree[x].rson,y);
		pushup(x);
		return x;
	}
	tree[y].lson=merge(x,tree[y].lson);
	pushup(y);
	return y;
}
inline void insert(const int val){
	int x,y;
	split(root,val,x,y);
	root=merge(merge(x,newnode(val)),y);
}
inline void erase(const int val){
	int x,y,z;
	split(root,val,x,z);
	split(x,val-1,x,y);
	y=merge(tree[y].lson,tree[y].rson);
	root=merge(merge(x,y),z);
}
inline int query_rank(const int val){
	int x,y;
	split(root,val-1,x,y);
	const int res=tree[x].size+1;
	root=merge(x,y);
	return res;
}
inline int query_val(const int root,const int rank){
	if(tree[tree[root].lson].size>=rank){
		return query_val(tree[root].lson,rank);
	}
	if(tree[tree[root].lson].size+1==rank){
		return tree[root].val;
	}
	return query_val(tree[root].rson,rank-tree[tree[root].lson].size-1);
}
inline int prev_of(const int val){
	int x,y;
	split(root,val-1,x,y);
	const int res=query_val(x,tree[x].size);
	root=merge(x,y);
	return res;
}
inline int next_of(const int val){
	int x,y;
	split(root,val,x,y);
	const int res=query_val(y,1);
	root=merge(x,y);
	return res;
}
int main(){
	srand(time(0));
	scanf("%d",&n);
	while(n--){
		int opt,val;
		scanf("%d %d",&opt,&val);
		if(opt==1){
			insert(val);
		}else if(opt==2){
			erase(val);
		}else if(opt==3){
			printf("%d\n",query_rank(val));
		}else if(opt==4){
			printf("%d\n",query_val(root,val));
		}else if(opt==5){
			printf("%d\n",prev_of(val));
		}else if(opt==6){
			printf("%d\n",next_of(val));
		}
	}
	return 0;
}

#include<bits/stdc++.h>
#define MAXN 50005
#define int long long
using namespace std;
struct node{
	int l,r,id,part;
}query[MAXN];
int n,m,k,res,a[MAXN],cnt[MAXN],ans[MAXN];
inline void add(int val){
	res-=cnt[val]*cnt[val];
	++cnt[val];
	res+=cnt[val]*cnt[val];
}
inline void del(int val){
	res-=cnt[val]*cnt[val];
	--cnt[val];
	res+=cnt[val]*cnt[val]; 
}
inline bool cmp(const node x,const node y){
	if(x.part!=y.part){
		return x.part<y.part;
	}
	return x.part&1?x.r<y.r:x.r>y.r;
}
signed main(){
	scanf("%lld %lld %lld",&n,&m,&k);
	for(int i=1;i<=n;++i){
		scanf("%lld",&a[i]);
	}
	n=sqrt(n);
	for(int i=1;i<=m;++i){
		scanf("%lld %lld",&query[i].l,&query[i].r);
		query[i].id=i;
		query[i].part=query[i].l/n;
	}
	sort(query+1,query+1+m,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;++i){
		while(l>query[i].l){
			add(a[--l]);
		}
		while(r<query[i].r){
			add(a[++r]);
		}
		while(l<query[i].l){
			del(a[l++]);
		}
		while(r>query[i].r){
			del(a[r--]);
		}
		ans[query[i].id]=res;
	}
	for(int i=1;i<=m;++i){
		printf("%lld\n",ans[i]);
	}
	return 0;
}

#include<bits/stdc++.h>
#define MAXN 300010
#define INF 1000000010
using namespace std;
struct Operator{
	int id,val;
}a[MAXN],lopt[MAXN],ropt[MAXN];
struct Query{
	int id,l,r,len;
}q[MAXN],lqry[MAXN],rqry[MAXN];
int n,m;
int b[MAXN],mp[MAXN],ans[MAXN];
inline int read(){
	int res=0;
	char c=getchar();
	while(!isdigit(c)){
		c=getchar();
	}
	while(isdigit(c)){
		res=(res<<1)+(res<<3)+(c^'0');
		c=getchar();
	}
	return res;
}
struct SegementTree{
	struct node{
		int l,r,Ldot,Rdot,dis; 
		node(int l=0,int r=0,int Ldot=-1,int Rdot=-1,int dis=INF){
			this->l=l;
			this->r=r;
			this->Ldot=Ldot;
			this->Rdot=Rdot;
			this->dis=dis;
		}
	}tree[MAXN<<2];
	inline node merge(const node &a,const node &b){
		if(a.Ldot==-1&&b.Ldot==-1){
			return node(a.l,b.r,-1,-1,INF);
		}
		if(b.Ldot==-1){
			return node(a.l,b.r,a.Ldot,a.Rdot,max(a.dis,b.r-a.Rdot));
		}
		if(a.Ldot==-1){
			return node(a.l,b.r,b.Ldot,b.Rdot,max(b.dis,b.Ldot-a.l));
		}
		return node(a.l,b.r,a.Ldot,b.Rdot,max(max(a.dis,b.dis),b.Ldot-a.Rdot-1));
	}
	inline void push_up(int root){
		tree[root]=merge(tree[root<<1],tree[root<<1|1]);
	}
	inline void build(const int root,const int l,const int r){
		tree[root].l=l;
		tree[root].r=r;
		if(l==r){
			tree[root]=node(l,r,-1,-1,INF);
			return;
		}
		int mid=(l+r)>>1;
		build(root<<1,l,mid);
		build(root<<1|1,mid+1,r);
		push_up(root);
	}
	inline void change(const int root,const int l,const int r,const int pos,const bool color){
		if(l==pos&&r==pos){
			if(color){
				tree[root]=node(pos,pos,pos,pos,0);
			}else{
				tree[root]=node(pos,pos,-1,-1,INF);
			}
			return;
		}
		int mid=(l+r)>>1;
		if(pos<=mid){
			change(root<<1,l,mid,pos,color);
		}else{
			change(root<<1|1,mid+1,r,pos,color);
		}
		push_up(root); 
	}
	inline node query(const int root,const int l,const int r,const int L,const int R){
		if(L<=l&&r<=R){
			return tree[root];
		}
		int mid=(l+r)>>1;
		node res;
		if(L<=mid&&mid<R){
			return merge(query(root<<1,l,mid,L,R),query(root<<1|1,mid+1,r,L,R));
		}
		if(L<=mid){
			return query(root<<1,l,mid,L,R);
		}
		return query(root<<1|1,mid+1,r,L,R);
	}
}Tree;
inline void solve(const int l,const int r,const int Lopt,const int Ropt,const int Lqry,const int Rqry){
	if(Rqry<Lqry){
		return;
	}
	if(l==r){
		for(register int i=Lqry;i<=Rqry;++i){
			ans[q[i].id]=l;
		}
		return;
	}
	const int mid=(l+r)>>1;
	register int OptLtop=0,OptRtop=0,QryLtop=0,QryRtop=0;
	for(register int i=Lopt;i<=Ropt;++i){
		if(a[i].val>=mid){
			Tree.change(1,1,n,a[i].id,true);
			ropt[++OptRtop]=a[i];
		}else{
			lopt[++OptLtop]=a[i];
		}
	}
	for(register int i=Lqry;i<=Rqry;++i){
		if(Tree.query(1,1,n,q[i].l,q[i].r).dis<q[i].len){
			rqry[++QryRtop]=q[i];
		}else{
			lqry[++QryLtop]=q[i];
		}
	}
	for(register int i=1;i<=OptLtop;++i){
		a[i+Lopt-1]=lopt[i];
	}
	for(register int i=1;i<=QryLtop;++i){
		q[i+Lqry-1]=lqry[i];
	}
	for(register int i=1;i<=OptRtop;++i){
		a[i+Lopt+OptLtop-1]=ropt[i];
	}
	for(register int i=1;i<=QryRtop;++i){
		q[i+Lqry+QryLtop-1]=rqry[i];
	}
	solve(l,mid,Lopt,Lopt+OptLtop-1,Lqry,Lqry+QryLtop-1); 
	for(register int i=Lopt;i<=Ropt;++i){
		if(a[i].val>=mid){
			Tree.change(1,1,n,a[i].id,false);
		}
	}
	solve(mid+1,r,Lopt+OptLtop,Ropt,Lqry+QryLtop,Rqry);
}
int main(){
	n=read();
	m=read();
	for(register int i=1;i<=n;++i){
		a[i].val=b[i]=read();
		a[i].id=i;
	}
	sort(b+1,b+1+n);
	const int inf=unique(b+1,b+1+n)-b-1;
	for(register int i=1;i<=n;++i){
		const int val=lower_bound(b+1,b+1+inf,a[i].val)-b;
		mp[val]=a[i].val;
		a[i].val=val;
	}
	for(register int i=1;i<=m;++i){
		q[i].l=read();
		q[i].r=read();
		q[i].len=read();
		q[i].id=i;
	}
	Tree.build(1,1,n);
	solve(1,inf+1,1,n,1,m);
	for(register int i=1;i<=m;++i){
		printf("%d\n",mp[ans[i]-1]);
	} 
	return 0;	
}

#include<bits/stdc++.h>
#define MAXN 300005
#define INF 1000000010
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
using namespace std;
struct Query{
	int id,l,r,len;
}q[MAXN];
int n,m,a[MAXN],b[MAXN];
vector<int> id[MAXN];
inline int read(){
	int res=0;
	char c=getchar();
	while(!isdigit(c)){
		c=getchar();
	}
	while(isdigit(c)){
		res=(res<<1)+(res<<3)+(c^'0');
		c=getchar();
	}
	return res;
}
struct SegementTree{
	struct node{
		int l,r,Lmax,Rmax,Max,len;
		int lson,rson; 
		node(int l=0,int r=0,int Lmax=0,int Rmax=0,int Max=0,int len=0,int lson=0,int rson=0){
			this->l=l;
			this->r=r;
			this->Lmax=Lmax;
			this->Rmax=Rmax;
			this->Max=Max;
			this->len=len;
			this->lson=lson;
			this->rson=rson;
		}
	}tree[MAXN*40];
	int cnt;
	inline node merge(const node &a,const node &b){
		node res;
		res.l=a.l;
		res.r=b.r;
		res.Lmax=a.Lmax;
		res.Rmax=b.Rmax;
		if(a.Lmax==a.len){
			res.Lmax+=b.Lmax;
		}
		if(b.Rmax==b.len){
			res.Rmax+=a.Rmax;
		}
		res.Max=max(max(a.Max,b.Max),a.Rmax+b.Lmax);
		res.len=a.len+b.len;
		return res;
	}
	inline void push_up(const int root){
		int lson=tree[root].lson,rson=tree[root].rson;
		tree[root]=merge(tree[lson],tree[rson]);
		tree[root].lson=lson;
		tree[root].rson=rson;
	}
	inline int build(const int l,const int r){
		const int root=++cnt;
		tree[root].l=l;
		tree[root].r=r;
		tree[root].Lmax=tree[root].Rmax=tree[root].Max=0;
		tree[root].len=r-l+1;
		if(l==r){
			return root;
		}
		const int mid=(l+r)>>1;
		tree[root].lson=build(l,mid);
		tree[root].rson=build(mid+1,r);
		return root;
	}
	inline int change(const int pre,const int l,const int r,const int pos){
		const int root=++cnt;
		tree[root]=tree[pre];
		if(l==r){
			tree[root].Lmax=tree[root].Rmax=tree[root].Max=1;
			return root;
		}
		const int mid=(l+r)>>1;
		if(pos<=mid){
			tree[root].lson=change(tree[pre].lson,l,mid,pos);
		}else{
			tree[root].rson=change(tree[pre].rson,mid+1,r,pos);
		}
		push_up(root);
		return root;
	}
	inline node query(const int root,const int l,const int r,const int L,const int R){
		if(L<=l&&r<=R){
			return tree[root];
		}
		const int mid=(l+r)>>1;
		if(R<=mid){
			return query(tree[root].lson,l,mid,L,R);
		}
		if(mid<L){
			return query(tree[root].rson,mid+1,r,L,R);
		}
		return merge(query(tree[root].lson,l,mid,L,R),query(tree[root].rson,mid+1,r,L,R));
	}
}Tree;
int root[MAXN],mp[MAXN];
int main(){
//    int sub=read();
//    string fin="data"+to_string(sub)+".in";
//    string fout="data"+to_string(sub)+".ans";
//    freopen(fin.c_str(),"r",stdin);
//    freopen(fout.c_str(),"w",stdout);
	scanf("%d %d",&n,&m);
	for(register int i=1;i<=n;++i){
		a[i]=b[i]=read();
	}
	sort(b+1,b+1+n);
	const int inf=unique(b+1,b+1+n)-b-1;
	for(register int i=1;i<=n;++i){
		const int val=lower_bound(b+1,b+1+inf,a[i])-b;
		mp[val]=a[i];
		a[i]=val;
		id[a[i]].push_back(i);
	}
	root[0]=Tree.build(1,n);
	for(register int i=1;i<=inf;++i){
		root[i]=root[i-1];
		for(register size_t j=0;j<id[i].size();++j){
			root[i]=Tree.change(root[i],1,n,id[i][j]);
		}
	}
	while(m--){
		const int L=read(),R=read(),len=read();
		register int l=1,r=inf;
		while(l<r){
			const int mid=(l+r)>>1;
			if(Tree.query(root[mid],1,n,L,R).Max<len){
				l=mid+1;
			}else{
				r=mid;
			}
		}
		printf("%d\n",mp[l]);
	}
	return 0;
}