UPDATE(L,R,v)
You should add v to all Ai where L ≤ i ≤ R

QUERY(L,R,v)

You should output the frequency of the number v in the range from Lth to Rth index in the array.

INPUT:

1
5 5
1 2 3 4 5
2 3 4 3
1 3 4 -2
2 3 4 3
1 4 4 -1
2 3 4 1

OUTPUT:

Case 1:
1
0
2

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define vin vector<int>
#define vll vector<long long>
#define pii pair<int,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define pq priority_queue
#define all(x) x.begin(),x.end()
#define mod 1000000007
#define cone __builtin_popcount
#define conel __builtin_popcountll
typedef vector<vector<ll> > matrixl;
typedef vector<vector<int> > matrix;
#define N 100009
#define SN 2000
#define L (100000/SN)+2

int a[N],c[L][2*N],lz[L];

void upd(int l,int r,int v)
{
    int lc = l/SN;
    int rc = r/SN;
    if(lc==rc)
    {
        for(int i=l;i<=r;i++)
        {
            //cout<<"T "<<i<<endl;
            c[lc][a[i]]--;
            a[i]+=v;
            c[lc][a[i]]++;
        }
        return;
    }
    for(int i=l;i<(lc+1)*SN;i++)
    {
        c[lc][a[i]]--;
        a[i]+=v;
        c[lc][a[i]]++;
    }
    for(int i = lc+1;i<rc;i++) lz[i]+=v;
    for(int i=rc*SN;i<=r;i++)
    {
        c[rc][a[i]]--;
        a[i]+=v;
        c[rc][a[i]]++;
    }
}

int qry(int l,int r,int v)
{
    int res = 0;
    int lc = l/SN;
    int rc = r/SN;
    if(lc==rc)
    {
        for(int i=l;i<=r;i++) if(a[i]+lz[lc]==v) res++;
        return res;
    }
    for(int i=l;i<(lc+1)*SN;i++)
    {
        if(a[i]+lz[lc]==v) res++;
    }
    for(int i=lc+1;i<rc;i++)
    {
        res+=c[i][v-lz[i]];
    }
    for(int i=rc*SN;i<=r;i++)
    {
        if(a[i]+lz[rc]==v) res++;
    }
    return res;
}

int main()
{
    int n,q,t,tp,x,y,v,test = 0;
    scanf("%d",&t);
    while(t--)
    {
        printf("Case %d:\n",++test);
        memset(c,0,sizeof(c));
        memset(lz,0,sizeof(lz));
        scanf("%d%d",&n,&q);
        for(int i=0; i<n; i++)
        {
            scanf("%d",&a[i]);
            c[i/SN][a[i]]++;
        }
        while(q--)
        {
            scanf("%d%d%d%d",&tp,&x,&y,&v);
            if(tp==1)
            {
                upd(x-1,y-1,v);
            }
            else
            {
                printf("%d\n",qry(x-1,y-1,v));
            }
            //for(int i=0;i<n;i++) cout<<a[i]<<" ";
            //cout<<endl;
        }
    }
}