#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
int n,m,a[N];
int tree[N<<2];
void pushup(int rt){
	tree[rt] = tree[rt*2] + tree[rt*2+1];
}
void build(int l,int r,int rt){
	if(l==r){
		tree[rt] = a[l];
		return;
	}
	int mid = (l+r)>>1;
	build(l,mid,rt*2);
	build(mid+1,r,rt*2+1);
	pushup(rt);
}
void update(int l,int r,int rt,int p,int c){
	if(l==r){
		tree[rt]+=c;
		return;
	}
	int mid = (l+r)/2;
	if(p<=mid)update(l,mid,rt<<1,p,c);
	else update(mid+1,r,rt<<1|1,p,c);
	pushup(rt);
}
int query(int l,int r,int rt,int L,int R)
{
	//L---l---r--R
	if(L<=l && r<=R){
		return tree[rt];
	}
	int res = 0;
	int mid = (l+r)>>1;
	if(L<=mid)res+=query(l,mid,rt<<1,L,R);
	if(R>mid)res+=query(mid+1,r,rt<<1|1,L,R);
	return res;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,n,1);
	for(int i=1;i<=m;i++){
		int op,x,y,z;
		cin>>op>>x>>y;
		if(op==1){
			update(1,n,1,x,y);
		}
		else{
			cout<<query(1,n,1,x,y)<<endl;
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+5;
int T,n,m,tree[N<<2];
void pushup(int rt){
	tree[rt] = tree[rt<<1]*tree[rt<<1|1];
	tree[rt]%=m;
}
void build(int l,int r,int rt){
	if(l==r){
		tree[rt] = 1;
		return;
	}
	int mid = (l+r)>>1;
	build(l,mid,rt<<1);
	build(mid+1,r,rt<<1|1);
	pushup(rt);
}
void change(int l,int r,int rt,int p){
	if(l==r){
		tree[rt] = 1;
		return;
	}
	int mid = (l+r)>>1;
	if(p<=mid)change(l,mid,rt<<1,p);
	else change(mid+1,r,rt<<1|1,p);
	pushup(rt);
}
void update(int l,int r,int rt,int p,int c){
	if(l==r){
		if(c>0)tree[rt]*=c;
		return;
	}
	int mid = (l+r)>>1;
	if(p<=mid)update(l,mid,rt<<1,p,c);
	else update(mid+1,r,rt<<1|1,p,c);
	pushup(rt);
}
signed main(){
	cin>>T;
	while(T--){
		cin>>n>>m;
		build(1,n,1);
		
		for(int i=1;i<=n;i++){
			int op,x;
			cin>>op>>x;
			if(op==1){
				update(1,n,1,i,x);
				cout<<tree[1]%m<<endl;
			}
			else{
				change(1,n,1,x);
				cout<<tree[1]%m<<endl;
			}
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+5;
int n,m,c;
int tree[N<<2],tag[N<<2];
struct node{
	int s,t,k;
}p[N];
bool cmp(node a,node b){
	if(a.t==b.t)return a.s<b.s;
	return a.t<b.t;
}
void pushup(int rt){
	tree[rt] = max(tree[rt<<1],tree[rt<<1|1]);
}
void pushdown(int rt){
	if(tag[rt]){
		tag[rt<<1] += tag[rt];
		tag[rt<<1|1] += tag[rt];
		tree[rt<<1] += tag[rt];
		tree[rt<<1|1] += tag[rt];
		tag[rt] = 0;
	}
}
void update(int l,int r,int rt,int L,int R,int c)
{
	if(L<=l && r<=R){
		tree[rt]+=c;
		tag[rt]+=c;
		return;
	}
	pushdown(rt);
	int mid = (l+r)>>1;
	if(L<=mid)update(l,mid,rt<<1,L,R,c);
	if(R>mid)update(mid+1,r,rt<<1|1,L,R,c);
	pushup(rt);
}
int query(int l,int r,int rt,int L,int R){
	if(L<=l && r<=R){
		return tree[rt];
	}
	int res = 0;
	pushdown(rt);
	int mid = (l+r)>>1;
	if(L<=mid)res=max(res,query(l,mid,rt<<1,L,R));
	if(R>mid)res = max(res,query(mid+1,r,rt<<1|1,L,R));
	return res;
}
signed main(){
	cin>>n>>m>>c;
	for(int i=1;i<=n;i++){
		cin>>p[i].s>>p[i].t>>p[i].k;
	}
	int res = 0;
	sort(p+1,p+n+1,cmp);
	for(int i=1;i<=n;i++){
		int l=p[i].s,r=p[i].t,k=p[i].k;
		int Max = query(1,m,1,l,r-1);
		if(Max>=c)continue;
		else {
			if(Max+k<=c){
				res+=k;
				update(1,m,1,l,r-1,k);
			}
			else{
				res+=c-Max;
				update(1,m,1,l,r-1,c-Max);
			}
		}
	}
	cout<<res<<endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+5;
int n,m,tree[N<<2],tag[N<<2],a[N];
void pushup(int rt){
	tree[rt] = tree[rt<<1] + tree[rt<<1|1];
}
void pushdown(int l,int r,int rt){
	if(tag[rt]){
		tag[rt<<1] += tag[rt];
		tag[rt<<1|1] += tag[rt];
		int mid = (l+r)>>1;
		tree[rt<<1] += tag[rt]*(mid-l+1);
		tree[rt<<1|1] += tag[rt]*(r-mid);
		tag[rt] = 0;
	}
}
void build(int l,int r,int rt){
	if(l==r){
		tree[rt] = a[l];
		return;
	}
	int mid = (l+r)>>1;
	build(l,mid,rt<<1);
	build(mid+1,r,rt<<1|1);
	pushup(rt);
}
void update(int l,int r,int rt,int L,int R,int c){
	if(L<=l && r<=R){
		tree[rt]+=c*(r-l+1);
		tag[rt]+=c;
		return;
	}
	pushdown(l,r,rt);
	int mid = (l+r)>>1;
	if(L<=mid)update(l,mid,rt<<1,L,R,c);
	if(R>mid)update(mid+1,r,rt<<1|1,L,R,c);
	pushup(rt);
}
int query(int l,int r,int rt,int L,int R){
	if(L<=l && r<=R){
		return tree[rt];
	}
	int mid = (l+r)>>1;
	pushdown(l,r,rt);
	int res = 0;
	if(L<=mid)res+=query(l,mid,rt<<1,L,R);
	if(R>mid)res+=query(mid+1,r,rt<<1|1,L,R);
	return res;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,n,1);
	while(m--){
		int op,x,y,z;
		cin>>op>>x>>y;
		if(op==1){
			cin>>z;
			update(1,n,1,x,y,z);
		}
		else{
			cout<<query(1,n,1,x,y)<<endl;
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
double a[N],tree1[N<<2],tree2[N<<2],tag[N<<2];
int n,m;
void pushup(int rt)
{
	tree1[rt] = tree1[rt<<1]+tree1[rt<<1|1];
	tree2[rt] = tree2[rt<<1]+tree2[rt<<1|1];
}
void pushdown(int l,int r,int rt)
{
	if(tag[rt]!=0){
		tag[rt<<1]+=tag[rt];
		tag[rt<<1|1]+=tag[rt];
		int mid = (l+r)>>1;
		tree2[rt<<1] = tree2[rt<<1] + 2*tag[rt]*tree1[rt<<1] + tag[rt]*tag[rt]*(mid-l+1);
		tree2[rt<<1|1] = tree2[rt<<1|1] + 2*tag[rt]*tree1[rt<<1|1] + tag[rt]*tag[rt]*(r-mid);
		tree1[rt<<1] += tag[rt]*(mid-l+1);
		tree1[rt<<1|1] += tag[rt]*(r-mid);
		tag[rt] = 0;
	}
}
void build(int l,int r,int rt)
{
	if(l==r){
		tree1[rt] = a[l];
		tree2[rt] = a[l]*a[l];
		return;
	}
	int mid = (l+r)>>1;
	build(l,mid,rt<<1);
	build(mid+1,r,rt<<1|1);
	pushup(rt);
}
void update(int l,int r,int rt,int L,int R,double c)
{
	if(L<=l && r<=R){
		tag[rt]+=c;
		tree2[rt] = tree2[rt]+2*c*tree1[rt] + c*c*(r-l+1);
		tree1[rt] += c*(r-l+1);
		return;
	}
	pushdown(l,r,rt);
	int mid = (l+r)>>1;
	if(L<=mid)update(l,mid,rt<<1,L,R,c);
	if(R>mid)update(mid+1,r,rt<<1|1,L,R,c);
	pushup(rt);
}
double query1(int l,int r,int rt,int L,int R)
{
	double sum = 0;
	if(L<=l && r<=R){
		return tree1[rt];
	}
	pushdown(l,r,rt);
	int mid = (l+r)>>1;
	if(L<=mid)sum+=query1(l,mid,rt<<1,L,R);
	if(R>mid)sum+=query1(mid+1,r,rt<<1|1,L,R);
	return sum; 
}
double query2(int l,int r,int rt,int L,int R)
{
	if(L<=l && r<=R){
		return tree2[rt];
	}
	pushdown(l,r,rt);
	double sum = 0;
	int mid = (l+r)>>1;
	if(L<=mid)sum+=query2(l,mid,rt<<1,L,R);
	if(R>mid)sum+=query2(mid+1,r,rt<<1|1,L,R);
	return sum;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,n,1);
	for(int i=1;i<=m;i++){
		int pos,x,y;
		cin>>pos;
		if(pos==1){
			double z;
			cin>>x>>y>>z;
			update(1,n,1,x,y,z);
		}
		if(pos==2){
			cin>>x>>y;
			double sum = query1(1,n,1,x,y);
			cout<<fixed<<setprecision(4)<<sum/(y-x+1)<<endl;
		}
		if(pos==3){
			cin>>x>>y;
			double sum1 = query1(1,n,1,x,y);
			double ave = sum1/(y-x+1);
			double sum2 = query2(1,n,1,x,y);
			double len = (y-x+1);
			cout<<fixed<<setprecision(4)<<(sum2-2*sum1*ave+len*ave*ave)/len<<endl;
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int n,m;
struct node{
	int l,r,cnt,flag;
	friend node operator + (node a,node b){
		node c;
		if(a.flag==1)c.l = b.l;
		else c.l = a.l;
		if(b.flag==1)c.r=a.r;
		else c.r = b.r;
		c.cnt = a.cnt+b.cnt + (a.r==1&&b.l==1);
		if(a.flag==1 && b.flag==1)c.flag = 1;
		else c.flag = 0;
		return c;
	}
}tree[N<<2];
void pushup(int rt){
	tree[rt] = tree[rt<<1] + tree[rt<<1|1];
}
void build(int l,int r,int rt){
	if(l==r){
		if(l==1)tree[rt] = {0,1,0,0};
		else if(l==n)tree[rt] = {1,0,0,0};
		else tree[rt] = {0,0,0,1};
		return;
	}
	int mid = (l+r)>>1;
	build(l,mid,rt<<1);
	build(mid+1,r,rt<<1|1);
	pushup(rt);
}
void update(int l,int r,int rt,int p,char c){
	if(l==r){
		if(c=='X'){
			tree[rt] = {0,0,0,1};
		}
		else if(c=='('){
			tree[rt] = {0,1,0,0};
		}
		else if(c==')'){
			tree[rt] = {1,0,0,0};
		}
		return;
	}
	int mid = (l+r)>>1;
	if(p<=mid)update(l,mid,rt<<1,p,c);
	else update(mid+1,r,rt<<1|1,p,c);
	pushup(rt);
}
node query(int l,int r,int rt,int L,int R){
	if(L<=l && r<=R){
		return tree[rt];
	}
	int mid = (l+r)>>1;
	if(R<=mid)return query(l,mid,rt<<1,L,R);
	else if(L>mid)return query(mid+1,r,rt<<1|1,L,R);
	else return query(l,mid,rt<<1,L,R)+query(mid+1,r,rt<<1|1,L,R);
}
int main(){
	cin>>n>>m;
	build(1,n,1);
	for(int i=1;i<=m;i++){
		int op,x,y;
		char c;
		cin>>op>>x;
		if(op==1){
			cin>>c;
			update(1,n,1,x,c);
		}
		else{
			cin>>y;
			node tmp = query(1,n,1,x,y);
			cout<<tmp.cnt<<endl;
		}
	}
	return 0;
}