#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define get(i) ((i - 1) / len + 1)
using namespace std;
const int N = 1e5 + 5;

int len;
int tim[405][N], num[405][405], a[N], temp[N];

int query(int l, int r)
{
    int res = 0;
    if (get(l) == get(r))
    {
        for (int i = l; i <= r; i++)
            temp[a[i]]++;
        for (int i = l; i <= r; i++)
        {
            if (temp[a[i]] > 0 && temp[a[i]] % 2 == 0)
                res++;
            temp[a[i]] = 0;
        }
    }
    else 
    {
        int i = l, j = r;
        res += num[get(i) + 1][get(j) - 1];
        while (get(i) == get(l))
        {
            temp[a[i]]++;
            if ((temp[a[i]] + tim[get(j) - 1][a[i]] - tim[get(i)][a[i]]) > 0 
                && (temp[a[i]] + tim[get(j) - 1][a[i]] - tim[get(i)][a[i]]) % 2 == 0)
                res++;
            else if ((temp[a[i]] + tim[get(j) - 1][a[i]] - tim[get(i)][a[i]]) > 1 
                && (temp[a[i]] + tim[get(j) - 1][a[i]] - tim[get(i)][a[i]]) % 2)
                res--;
            i++;
        }
        while (get(j) == get(r))
        {
            temp[a[j]]++;
            if ((temp[a[j]] + tim[get(j) - 1][a[j]] - tim[get(i) - 1][a[j]]) > 0 
                && (temp[a[j]] + tim[get(j) - 1][a[j]] - tim[get(i) - 1][a[j]]) % 2 == 0)
                res++;
            else if ((temp[a[j]] + tim[get(j) - 1][a[j]] - tim[get(i) - 1][a[j]]) > 1 
                && (temp[a[j]] + tim[get(j) - 1][a[j]] - tim[get(i) - 1][a[j]]) % 2)
                res--;
            j--;
        }
        for (int k = l; k < i; k++)
            temp[a[k]] = 0;
        for (int k = j + 1; k <= r; k++)
            temp[a[k]] = 0;
    }
    return res;
}

int main()
{
    int n, c, m;
    scanf("%d%d%d", &n, &c, &m);
    len = sqrt(n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        tim[get(i)][a[i]]++;
    }
    for (int i = 1; i <= get(n); i++)
    {
        for (int j = 0; j <= c; j++)
            tim[i][j] += tim[i - 1][j];
    }
    for (int i = 1; i <= get(n); i++)
    {
        memset(temp, 0, sizeof(temp));
        for (int j = i; j <= get(n); j++)
        {
            int r = j * len;
            num[i][j] = num[i][j - 1];
            for (int k = (j - 1) * len + 1; k <= r; k++)
            {
                temp[a[k]]++;
                if (temp[a[k]] > 0 && temp[a[k]] % 2 == 0)
                    num[i][j]++;
                else if (temp[a[k]] > 1 && temp[a[k]])
                    num[i][j]--;
            }
        }
    }
    memset(temp, 0, sizeof(temp));
    int ans = 0;
    while (m--)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        l = (l + ans) % n + 1, r = (r + ans) % n + 1;
        if (l > r)
            swap(l, r);
        printf("%d\n", ans = query(l, r));
    }
}

#include <bits/stdc++.h>
using namespace std;
int L[45],R[45],pos[40005],a[40005],b[40005],c[45][45][40005],raw[40005],mx[45][45],d[40005];
int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    int t=(int)cbrt(n);

    for(int i=1; i<=t; i++) {
        L[i]=(i-1)*(n/t)+1;
        R[i]=i*(n/t);
    }
    if(R[t]<n) {
        t++;
        L[t]=R[t-1]+1;
        R[t]=n;
    }
    for(int i=1; i<=t; i++) {
        for(int j=L[i]; j<=R[i]; j++) {
            pos[j]=i;
        }
    }

    for(int i=1; i<=n; i++) scanf("%d",a+i);
    memcpy(b,a,sizeof(b));
    sort(b+1,b+1+n);
    int cnt=unique(b+1,b+1+n)-b-1;
    for(int i=1; i<=n; i++) {
        int tmp=lower_bound(b+1,b+1+cnt,a[i])-b;
        raw[tmp]=a[i];
        a[i]=tmp;
    }

    for(int i=1; i<=t; i++) {
        for(int j=i; j<=t; j++) {
            for(int k=L[i]; k<=R[j]; k++) {
                c[i][j][a[k]]++;
                if(c[i][j][a[k]]>c[i][j][mx[i][j]]||(c[i][j][a[k]]==c[i][j][mx[i][j]]&&a[k]<mx[i][j])) mx[i][j]=a[k];
            }
        }
    }

    int x=0;
    while(m--) {
        int l,r;
        scanf("%d%d",&l,&r);
        l=(l+x-1)%n+1;
        r=(r+x-1)%n+1;
        if(l>r) swap(l,r);
        int pl=pos[l],pr=pos[r];
        if(pl==pr) {
            x=0;
            for(int i=l; i<=r; i++) {
                d[a[i]]++;
                if(d[a[i]]>d[x]||(d[a[i]]==d[x]&&a[i]<x)) x=a[i];
            }
            for(int i=l; i<=r; i++) d[a[i]]--;
            x=raw[x];
            printf("%d\n",x);
            continue;
        }
        x=mx[pl+1][pr-1];
        for(int i=l; i<=R[pl]; i++) {
            c[pl+1][pr-1][a[i]]++;
            if(c[pl+1][pr-1][a[i]]>c[pl+1][pr-1][x]||(c[pl+1][pr-1][a[i]]==c[pl+1][pr-1][x]&&a[i]<x)) x=a[i];
        }
        for(int i=L[pr]; i<=r; i++) {
            c[pl+1][pr-1][a[i]]++;
            if(c[pl+1][pr-1][a[i]]>c[pl+1][pr-1][x]||(c[pl+1][pr-1][a[i]]==c[pl+1][pr-1][x]&&a[i]<x)) x=a[i];
        }
        x=raw[x];
        printf("%d\n",x);
        for(int i=l; i<=R[pl]; i++) c[pl+1][pr-1][a[i]]--;
        for(int i=L[pr]; i<=r; i++) c[pl+1][pr-1][a[i]]--;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

int n;
int opt[100010],opv[100010];

struct discreator{
    int ori_val[100010];
    int tot;
    int new_val[100010];
    int range;

    void init(){
        tot=0;
        range=0;    
    }

    void build(){
        sort(ori_val+1,ori_val+1+tot);

        for(int i=1;i<=n;i++){
            if(i==1||ori_val[i]!=ori_val[i-1]){
                new_val[++range]=ori_val[i];
            }
        }   
    }

    int query(int x){
        return lower_bound(new_val+1,new_val+range+1,x)-new_val;
    }

}dis;

struct binary_indexed_tree{
    int val[100010];
    int lg;

    void init(){
        memset(val,0,sizeof(val));

    }

    int lowbit(int x){
        return x&(-x);
    }

    void insert(int x,int y){
        for(;x<=dis.range;x+=lowbit(x))val[x]+=y;
    }

    int query(int x){
        int ans=0;
        for(;x;x-=lowbit(x))ans+=val[x];
        return ans;
    }

    int got(int x){//binary divide
        int t=0;
        for(int i=lg;i>=0;i--){
            t+=1<<i;
            if(t>dis.range||val[t]>=x){
                t-=1<<i;
            }
            else x-=val[t];
        }
        return t+1;
    }
}bit;

struct previous_und_next{
    multiset<int>greater_;
    multiset<int>less_;
    multiset<int>::iterator it;

    void init(){
        greater_.clear();
        less_.clear();
    }

    void insert(int x){
        greater_.insert(x);
        less_.insert(-x);
    }

    int get_pre(int x){
        it=less_.upper_bound(-x);
        int ret=*it;
        ret=-ret;
        return ret;
    }

    int get_next(int x){
        it=greater_.upper_bound(x);
        int ret=*it;
        return ret;
    }

    int del(int x){
        if(greater_.find(x)!=greater_.end())
        greater_.erase(greater_.find(x));

        if(less_.find(-x)!=less_.end())
        less_.erase(less_.find(-x));
    }
}pun;

int main(){
    ios::sync_with_stdio(false);

    dis.init();
    bit.init();
    pun.init();

    cin>>n;

    for(int i=1;i<=n;i++){
        cin>>opt[i]>>opv[i];
        dis.ori_val[++dis.tot]=opv[i];
    }

    dis.build();
    bit.lg=(int)floor(log(dis.range*1.0)/log(2));

    int cod;
    for(int i=1;i<=n;i++){
        cod=dis.query(opv[i]);
        if(opt[i]==1){
            bit.insert(cod,1);
            pun.insert(cod);
        }
        if(opt[i]==2){
            bit.insert(cod,-1);
            pun.del(cod);
        }
        if(opt[i]==3){
            cout<<bit.query(cod-1)+1<<endl;
        }
        if(opt[i]==4){
            cout<<dis.new_val[bit.got(opv[i])]<<endl;
        }
        if(opt[i]==5){
            cout<<dis.new_val[pun.get_pre(cod)]<<endl;
        }
        if(opt[i]==6){
            cout<<dis.new_val[pun.get_next(cod)]<<endl;
        }
    }

    return 0;
}

#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<stdio.h>
#define ll long long
#define ull unsigned long long
using namespace std;

int n,m;
ll dp[12][1<<11];
bool in[1<<11]; 

int main(){
    while(cin>>n>>m&&n&&m){
        memset(dp,0,sizeof(dp));
        memset(in,false,sizeof(in));
        for(int i=0;i< 1<<m;i++){
            bool cnt=false,odd=false;
            for(int j=0;j<m;j++){
                if(i>>j&1){
                    odd|=cnt;
                    cnt=false;
                }
                else cnt^=1;
            }
            in[i]=odd|cnt?0:1;
        }
        dp[0][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=0;j< 1<<m;j++){
                dp[i][j]=0;
                for(int k=0;k< 1<<m;k++){
                    if((j&k)==0&&in[j|k]){
                        dp[i][j]+=dp[i-1][k];
                    }
                }
            }
        }
        cout<<dp[n][0]<<endl;
    }
    return 0;
}

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>

using namespace std;
int n;
int seq[310];
int qzh[310];
int dp[310][310];
int s[310][310];



int main(){
    memset(dp,0x3f,sizeof(dp));
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>seq[i];
        dp[i][i]=0;
        qzh[i]=qzh[i-1]+seq[i];
    }

    for(int len=2;len<=n;len++){
        //mei jv zone length
        for(int i=1;i+len-1<=n;i++){

            int j=i+len-1;
            for(int k=i;k<j;k++){
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
            }
            dp[i][j]+=qzh[j]-qzh[i-1];
        }
    }
    cout<<dp[1][n];
    return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int u=50010;
int ver[2*u],edge[2*u],nxt[2*u],head[u],a[u],b[u],g[u],v[u],fa[u][16],sh[u],on[u];
long long c[u],d[u],f[u],dis[u][16],l,r,mid,sum;
int n,m,t,tot,x,y,z,i;
vector<long long> arv[u];
queue<int> q;
void add(int ycat_l,int ycat_h,int ycat_v)
{
    ver[++tot]=ycat_h,edge[tot]=ycat_v,nxt[tot]=head[ycat_l],head[ycat_l]=tot;
}

void bfs()
{
    int i,j,x,y;
    v[1]=1;
    for(i=head[1];i;i=nxt[i])
    {
        q.push(ver[i]),v[ver[i]]=1;
        b[++t]=i,sh[ver[i]]=t;
    }
    while(q.size())
    {
        x=q.front(),q.pop();
        for(i=head[x];i;i=nxt[i])
          if(!v[y=ver[i]])
          {
                q.push(y),v[y]=1;
                fa[y][0]=x,dis[y][0]=edge[i];
                for(j=1;j<16;j++)
                  fa[y][j]=fa[fa[y][j-1]][j-1],dis[y][j]=dis[y][j-1]+dis[fa[y][j-1]][j-1];
            }
    }
}

bool dfs(int x)
{
    v[x]=1;
    if(!sh[x]&&on[x]) return 1;
    bool flag=0;
    for(int i=head[x];i;i=nxt[i])
      if(!v[ver[i]])
        {
            flag=1;
            if(!dfs(ver[i])) return 0;
        }
    return flag;
}

bool solve(long long T)
{
    int p,q,i,j;
    for(i=1;i<=t;i++)
      while(arv[i].size()) arv[i].pop_back();
    memset(v,0,sizeof(v));
    memset(on,0,sizeof(on));
    v[1]=1;
    for(i=1;i<=m;i++)
    {
      for(g[i]=a[i],d[i]=0,j=15;j>=0;j--)
            if(fa[g[i]][j]&&d[i]+dis[g[i]][j]<=T) d[i]+=dis[g[i]][j],g[i]=fa[g[i]][j];
        on[g[i]]=1;
        if(j=sh[g[i]])
        {
            arv[j].push_back(T-d[i]);
            if(arv[j].size()>1&&T-d[i]>arv[j][arv[j].size()-2]) swap(arv[j][arv[j].size()-1],arv[j][arv[j].size()-2]);
        }
    }
    for(i=1,p=q=0;i<=t;i++)
    {
      if(!dfs(ver[b[i]]))
            if(arv[i].size()&&arv[i][arv[i].size()-1]<edge[b[i]]*2) arv[i].pop_back(); else f[++q]=edge[b[i]];
      for(j=0;j<arv[i].size();j++)
        if(arv[i][j]>=edge[b[i]]) c[++p]=arv[i][j]-edge[b[i]];
    }
    sort(c+1,c+p+1);
    sort(f+1,f+q+1);
    if(p<q) return 0;
    for(i=q,j=p;i;i--,j--)
      if(c[j]<f[i]) return 0;
    return 1;
}

int main()
{
    cin>>n;
    for(i=1;i<n;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z),add(y,x,z),sum+=z;
    }
    cin>>m;
    for(i=1;i<=m;i++) scanf("%d",&a[i]);
    bfs();
    l=0,r=sum+1;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(solve(mid)) r=mid; else l=mid+1;
    }
    if(l>sum) l=-1;
    cout<<l<<endl;
    return 0;
}

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<functional>
#include<utility>
#include<vector>
using namespace std;
typedef pair<int,int> pp;

int n,m;
//priority_queue<pp,vector<pp>,greater<pp> >q;
//len dat
int way[1010];

struct graphic{

    int edge[1010][1010];
    int cb[1010][1010];

    void init(){

        memset(edge,0x3f,sizeof(edge));
        memset(cb,0,sizeof(cb));
    }

    void add(int x,int y,int z){
        if(z<edge[x][y]){
            edge[x][y]=z;
            cb[x][y]=1;
        }
        else if(z==edge[x][y]){
            cb[x][y]++;
        }
        if(z<edge[y][x]){
            edge[y][x]=z;
            cb[y][x]=1;
        }
        else if(z==edge[y][x]){
            cb[y][x]++;
        }
    }

    int dist[1010];
    bool vis[1010];

    void djs(){
        memset(dist,0x3f,sizeof(dist));
        memset(vis,false,sizeof(vis));
        dist[1]=0;

        for(int i=1;i<n;i++){
            int x=0;
            for(int j=1;j<=n;j++){
                if(!vis[j]&&(x==0||dist[j]<dist[x]))x=j;
            }
            vis[x]=1;
            for(int j=1;j<=n;j++){
                dist[j]=min(dist[j],dist[x]+edge[x][j]);
            }
        }
    }

    bool belong[1010];
    void prim(){
        memset(belong,false,sizeof(belong));
        pp poi[1010];
        belong[1]=true;
        for(int i=2;i<=n;i++){
            poi[i]=(pp){dist[i],i};

        }
        sort(poi+1,poi+1+n);
        for(int i=2;i<=n;i++){
            int nowa=poi[i].second;
            belong[nowa]=true;
            for(int j=1;j<=n;j++){
                if(dist[nowa]==dist[j]+edge[nowa][j]){
                    way[nowa]+=cb[nowa][j];
                }
            }
        }
    }
}g;



unsigned long long ans;
int main(){
    cin>>n>>m;
    int u,v,w;
    g.init();
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        g.add(u,v,w);
    }
    g.djs();
    memset(way,0,sizeof(way));
    way[1]=1;
    g.prim();
    ans=1;
    for(int i=1;i<=n;i++){
        ans*=way[i];
        ans%=0x7fffffff;
    }
    cout<<ans;
    return 0;
}

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

int n,t,s,e;
struct discreator{
    int tot;
    int val[1010];

    void init(){
        tot=0;
        memset(val,0,sizeof(val));
    }

    int query(int x){
        return val[x];
    }

    void insert(int x){
        if(!val[x]){
            tot++;
            val[x]=tot;
        }
    }
}mmp;

struct graphic{
    int siz;
    long long len[210][210];
    void init(){
        memset(len,0x3f,sizeof(len));
        siz=0;
    }   
    void init2(){
        memset(len,0,sizeof(len));
    }
    void add(int x,int y,long long z){
        len[x][y]=min(len[x][y],z);
        len[y][x]=min(len[x][y],z);
    }
}og,ng;

graphic operator * (const graphic x,const graphic y){
    graphic ret;
    ret.init();
    for(int i=1;i<=mmp.tot;i++){
        for(int j=1;j<=mmp.tot;j++){
            for(int k=1;k<=mmp.tot;k++){
                ret.len[i][j]=min(ret.len[i][j],x.len[i][k]+y.len[k][j]);
            }
        }
    }

    return ret;
}

graphic ksm(int x){
    graphic ret=og;
    x--;
    while(x){
        if(x&1)ret=ret*og;
        og=og*og;
        x=x>>1;
    }

    return ret;
}

int main(){
    mmp.init();
    cin>>n>>t>>s>>e;
    /////////////////////////////
    int bg,ed;
    if(!mmp.query(s)){
        mmp.insert(s);
    }
    bg=mmp.query(s);
    /////////////////////////////
    if(!mmp.query(e)){
        mmp.insert(e);
    }
    ed=mmp.query(e);
    /////////////////////////////
    og.init();
    for(int i=1;i<=t;i++){
        int u,v,w;
        cin>>w>>u>>v;
        int ut,vt;
        if(!mmp.query(u)){
            mmp.insert(u);
        }
        ut=mmp.query(u);
        og.siz=max(og.siz,ut);
        /////////////////////////
        if(!mmp.query(v)){
            mmp.insert(v);
        }
        vt=mmp.query(v);
        og.siz=max(og.siz,vt);
        /////////////////////////
        og.add(ut,vt,w);
    }

    ng=ksm(n);

    cout<<min(ng.len[bg][ed],ng.len[ed][bg]);
    return 0;
}

#include<iostream>
#include<algorithm>
#include<functional>
#include<queue>
#include<cstring>
#include<utility>
#include<vector>
#include<cmath>
using namespace std;
typedef pair<int,int> pp;

priority_queue< pp , vector<pp> , greater<pp> >q;

int val[100010],l[1000010],r[100010];
bool tog[100010];
int n,m;

int main(){
    cin>>n>>m;
    memset(tog,false,sizeof(tog));
    int res=0;
    int tmp;
    int tot=0;
    for(int i=1;i<=n;i++){
        cin>>tmp;
        if(!tmp)continue;
        if(!tot||tmp*val[tot]<0){
            val[++tot]=tmp;
        }
        else val[tot]+=tmp;

    }
    int cz=0;
    for(int i=1;i<=tot;i++){
        l[i]=i-1;
        r[i]=i+1;
        if(val[i]>0){
            cz++;
            res+=val[i];
        }
        q.push(make_pair(abs(val[i]),i));
    }

    while(cz>m){
        while(!q.empty()&&tog[q.top().second]){
            q.pop();
        }
        pp t=q.top();
        q.pop();

        if(val[t.second]>0||(l[t.second]!=0&&r[t.second]!=tot+1)){
            res-=t.first;
            val[t.second]+=val[l[t.second]]+val[r[t.second]];
            q.push(make_pair(abs(val[t.second]),t.second));

            tog[l[t.second]]=true;
            tog[r[t.second]]=true;
            int lt=l[t.second];
            int rt=r[t.second];
            r[l[lt]]=r[lt];
            l[r[lt]]=l[lt];
            l[r[rt]]=l[rt];
            r[l[rt]]=r[rt];

            cz--;
        }
    }
    cout<<res;
    return 0;
}

#include<iostream>
#include<queue>
#include<vector>
#include<functional>
using namespace std;

priority_queue<int,vector<int>,less<int> >q1;
priority_queue<int,vector<int>,greater<int> >q2;
int m,n;
int a[30010],u[30010];

int main(){

    cin>>m>>n;
    for(int i=1;i<=m;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>u[i];
    }

    for(int i=1;i<=n;i++){

        while(q1.size()+q2.size()<u[i]){
            q2.push(a[q1.size()+q2.size()+1]);
        }

        while(!q1.empty()&&q2.top()<q1.top()){
            q2.push(q1.top());
            q1.pop();
            q1.push(q2.top());
            q2.pop();
        }

        cout<<q2.top();
        cout<<endl;
        q1.push(q2.top());
        q2.pop();
    }
}