#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int N=2e5+5;
ll w[N],num[N];
ll read()
{
	ll x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
struct Node{int l,r;ll sz,sum;}t[N*4];
void build(int idx,int l,int r)
{
	t[idx].l=l,t[idx].r=r,t[idx].sz=t[idx].sum=0;
	if(l==r)return;
	int mid=(l+r)>>1;
	build(idx<<1,l,mid),build(idx<<1|1,mid+1,r);
}
void ins(int idx,int x)
{
	if(t[idx].l==t[idx].r){t[idx].sz++,t[idx].sum+=num[x];return;}
	int mid=(t[idx].l+t[idx].r)>>1;
	if(x<=mid)ins(idx<<1,x);else ins(idx<<1|1,x);
	t[idx].sz=t[idx<<1].sz+t[idx<<1|1].sz;
	t[idx].sum=t[idx<<1].sum+t[idx<<1|1].sum;
}
int que(int idx,ll x)
{
	if(x<=0)return 0;
	if(t[idx].l==t[idx].r)return x/num[t[idx].l]+(x%num[t[idx].l]>0);
	if(t[idx<<1|1].sum>=x)return que(idx<<1|1,x);
	return t[idx<<1|1].sz+que(idx<<1,x-t[idx<<1|1].sum);
}
int main()
{
	int q=read();
	while(q--)
	{
		int n,tot=0;
		ll m,sum=0;
		n=read(),m=read();
		for(int i=1;i<=n;i++)w[i]=read(),num[++tot]=w[i];
		sort(num+1,num+1+tot);
		tot=unique(num+1,num+1+tot)-num-1;
		build(1,1,tot);
		for(int i=1;i<=n;i++)
		{
			sum+=w[i];
			printf("%d ",que(1,sum-m));
			int x=lower_bound(num+1,num+1+tot,w[i])-num;
			ins(1,x);
		}
		puts("");
	}
	return 0;
}

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int N=1e5+5;
const int M=2e7+10;
int n,m,swp[N],bloc,a[N],pre[N],qcnt,mcnt,inq[N],l,r;
ll res[N],num[M],ans;
ll read()
{
	ll x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
struct Node
{
	int l,r,now,id;
	Node(int l=0,int r=0,int now=0,int id=0):l(l),r(r),now(now),id(id){}
}q[N];
bool cmp(Node x,Node y)
{
	if((x.l-1)/bloc==(y.l-1)/bloc)
	{
		if((x.r-1)/bloc==(y.r-1)/bloc)return ((x.r-1)/bloc&1)?x.now<y.now:x.now>y.now;
		return x.r<y.r;
	}
	return x.l<y.l;
}
void exchange(int x)
{
	swap(a[x],a[x+1]);
	if(x>=l-1&&x<=r)
	{
		ans-=num[pre[x]]*(num[pre[x]]-1)/2;
		num[pre[x]]--;
		ans+=num[pre[x]]*(num[pre[x]]-1)/2;
	}
	pre[x]^=a[x]^a[x+1];
	if(x>=l-1&&x<=r)
	{
		ans-=num[pre[x]]*(num[pre[x]]-1)/2;
		num[pre[x]]++;
		ans+=num[pre[x]]*(num[pre[x]]-1)/2;
	}
}
void work(int x)
{
	int f=1;
	if(inq[x])f=-1;
	if(x==l)
	{
		ans-=num[pre[x-1]]*(num[pre[x-1]]-1)/2;
		num[pre[x-1]]+=f;
		ans+=num[pre[x-1]]*(num[pre[x-1]]-1)/2;
	}
	if(x==r)
	{
		ans-=num[pre[x]]*(num[pre[x]]-1)/2;
		num[pre[x]]+=f;
		ans+=num[pre[x]]*(num[pre[x]]-1)/2;
	}
	inq[x]^=1;
}
int main()
{
	clock_t start1=clock(),end1;
	while(~scanf("%d%d",&n,&m))
	{
		qcnt=mcnt=ans=0,bloc=pow(n,0.6666666666)+1;
		for(int i=1;i<=n;i++)a[i]=read(),pre[i]=pre[i-1]^a[i];
		for(int i=1;i<=m;i++)
		{
			int op=read();
			if(op==1)
			{
				int l=read(),r=read();
				++qcnt;
				q[qcnt]=Node(l,r,mcnt,qcnt);
			}
			else swp[++mcnt]=read();
		}
		sort(q+1,q+1+qcnt,cmp);
		l=1,r=0;
		for(int i=1;i<=qcnt;i++)
		{
			for(int j=q[i-1].now+1;j<=q[i].now;j++)exchange(swp[j]);
			for(int j=q[i-1].now;j>q[i].now;j--)exchange(swp[j]);
			while(l>q[i].l)--l,work(l);
			while(r<q[i].r)++r,work(r);
			while(l<q[i].l)work(l),l++;
			while(r>q[i].r)work(r),r--;
			ll len=q[i].r-q[i].l+1;
			res[q[i].id]=len*(len-1)/2+len-ans;
		}
		for(int i=1;i<=qcnt;i++)printf("%lld\n",res[i]);
		while(l<=r)work(l),l++;
	}
	return 0;
}