Description

In this paper, a sequence a1,...,ana1,...,an with length nn is given. The sequence a1,...,ana1,...,an is all 00 at first and has mm operations. In the second operation, all the numbers in the interval [li,ri][li,ri] and vivi are taken as larger values. Finally, Σ i=1ni ⊕ ai Σ i=1ni ⊕ ai is calculated, where ⊕ is exclusive or operation

Input

First, enter an integer TT to represent the number of use case groups. For each group of use cases, enter five integers n,m,X,Y,Zn,m,X,Y,Z, where X,Y,ZX,Y,Z is used to generate li,ri,vili,ri,vi

(1≤T≤100,1≤n≤105,1≤m≤5⋅106,0≤X,Y,Z<230)(1≤T≤100,1≤n≤105,1≤m≤5⋅106,0≤X,Y,Z<230)

Output

Output Σ i=1ni ⊕ ai Σ i=1ni ⊕ ai

Sample Input

4
1 10 100 1000 10000
10 100 1000 10000 100000
100 1000 10000 100000 1000000
1000 10000 100000 1000000 10000000

Sample Output

1031463378
1446334207
351511856
47320301347

Solution

Every operation L r vl r v is to change Ai Ai into max(ai,v),l ≤ i ≤ rmax(ai,v),l ≤ i ≤ r, maintain Min[t]Min[t] min [t], Tag[t]Tag[t] and number Num[t]Num[t] of the interval with line tree, if the current updated value VV does not exceed the previous TagTag value of the interval, then the current operation is invalid, otherwise, clear all the interval less than vv The NumNum array is mainly used to maintain the minimum value of the auxiliary maintenance interval, because only when a part of the interval is cleared can there be a value less than TagTag, that is, when num [t] < r − L + 1num [t] < r − l+1, there will be a number that needs to be changed into VV, and the minimum value of the interval is VV, otherwise the part does not need to be updated, and the minimum value of the interval does not change

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define maxn 100005
#define ls (t<<1)
#define rs ((t<<1)|1)
int Num[maxn<<2],Min[maxn<<2],Tag[maxn<<2];
int T,n,m;
void push_up(int t)
{
    Min[t]=min(Min[ls],Min[rs]);
    Num[t]=Num[ls]+Num[rs];
}
void build(int l,int r,int t)
{
    Num[t]=Min[t]=Tag[t]=0;
    if(l==r)
    {
        Min[t]=Tag[t]=0,Num[t]=1;
        return ;
    }
    int mid=(l+r)/2;
    build(l,mid,ls),build(mid+1,r,rs);
    push_up(t);
}
void modify(int l,int r,int t,int v)
{
    if(Tag[t]>=v)return ;
    Tag[t]=v;
    if(Num[t]<r-l+1)
    {
        Min[t]=v;
        Num[t]=r-l+1;
    }
}
void push_down(int l,int r,int t)
{
    if(!Tag[t])return ;
    int mid=(l+r)/2;
    modify(l,mid,ls,Tag[t]),modify(mid+1,r,rs,Tag[t]);
}
void clear(int l,int r,int t,int v)
{
    if(Min[t]>=v)return ;
    Tag[t]=0;
    if(l==r)
    {
        Min[t]=Num[t]=0;
        return ;
    }
    int mid=(l+r)/2;
    clear(l,mid,ls,v),clear(mid+1,r,rs,v);
    push_up(t);
}
void update(int L,int R,int l,int r,int t,int v)
{
    if(Min[t]>=v)return ;
    if(L<=l&&r<=R)
    {
        clear(l,r,t,v);
        modify(l,r,t,v);
        return ;
    }
    push_down(l,r,t);
    int mid=(l+r)/2;
    if(L<=mid)update(L,R,l,mid,ls,v);
    if(R>mid)update(L,R,mid+1,r,rs,v);
    push_up(t);
}
int query(int L,int R,int l,int r,int t)
{
    if(L<=l&&r<=R)return Min[t];
    int ans=INF;
    push_down(l,r,t);
    int mid=(l+r)/2;
    if(L<=mid)ans=min(ans,query(L,R,l,mid,ls));
    if(R>mid)ans=min(ans,query(L,R,mid+1,r,rs));
    return ans;
}
unsigned X,Y,Z;
unsigned F()
{
    X^=(X<<11);
    X^=(X>>4);
    X^=(X<<5);
    X^=(X>>14);
    unsigned W=X^(Y^Z);
    X=Y;
    Y=Z;
    Z=W;
    return Z;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%u%u%u",&n,&m,&X,&Y,&Z);
        build(1,n,1);
        int mod=1<<30;
        for(int i=1;i<=m;i++)
        {
            unsigned f1,f2,f3;
            f1=F();
            f2=F();
            f3=F();
            int L=min(f1%n+1,f2%n+1),R=max(f1%n+1,f2%n+1),v=f3%mod;
            update(L,R,1,n,1,v);
        }
        ll ans=0;
        for(int i=1;i<=n;i++)ans^=((ll)i*query(i,i,1,n,1));
        printf("%lld\n",ans);
    }
    return 0;
}