#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#include<ext/pb_ds/priority_queue.hpp>

#define pir pair<ll,int>

using namespace std;

typedef long long ll;

//typedef std::priority_queue<pir,vector<pir>,greater<pir> > heap;

//3840 ms

typedef __gnu_pbds::priority_queue<pir,greater<pir> > heap;//默认是pairing_heap_tag

//3304 ms

const int N=1e6+,M=1e7+;

const ll INF=1e15;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,m,T,rxa,rxc,rya,ryc,rp,a,b;

int x,y,z;

struct node{

    int v,w,next;

}e[M];

int cnt,head[N];ll dis[N];bool vis[N];

inline void add(int u,int v,int w){

    e[++cnt].v=v;e[cnt].w=w;e[cnt].next=head[u];head[u]=cnt;

}

heap q;

inline void dijkstra(){

    int S;

    for(int i=;i<=n;i++) dis[i]=INF;

    dis[S=]=;

    q.push(make_pair(dis[S],S));

    while(!q.empty()){

        pir t=q.top();q.pop();

        int x=t.second;

        if(vis[x]) continue;

        vis[x]=;

        for(int i=head[x];i;i=e[i].next){

            int v=e[i].v;

            if(!vis[v]&&dis[v]>dis[x]+e[i].w){

                dis[v]=dis[x]+e[i].w;

                q.push(make_pair(dis[v],v));

            }

        }

    }

}

int main(){

    n=read();m=read();

    T=read();rxa=read();rxc=read();rya=read();ryc=read();rp=read();

    m=m-T;

    x=rxc%rp;y=ryc%rp;

    a=min(x%n+,y%n+);

    b=max(y%n+,y%n+);

    while(T--) add(a,b,-*a);

    while(m--) x=read(),y=read(),z=read(),add(x,y,z);

    dijkstra();

    printf("%lld",dis[n]);

    return ;

}

English

Vietnamese

In this problem, you have to maintain a dynamic set of numbers which support the two fundamental operations

• INSERT(S,x): if x is not in S, insert x into S
• DELETE(S,x): if x is in S, delete x from S

and the two type of queries

• K-TH(S) : return the k-th smallest element of S
• COUNT(S,x): return the number of elements of S smaller than x

Input

• Line 1: Q (1 ≤ Q ≤ 200000), the number of operations
• In the next Q lines, the first token of each line is a character I, D, K or C meaning that the corresponding operation is INSERT, DELETE, K-TH or COUNT, respectively, following by a whitespace and an integer which is the parameter for that operation.

If the parameter is a value x, it is guaranteed that 0 ≤ |x| ≤ 109. If the parameter is an index k, it is guaranteed that 1 ≤ k ≤ 109.

Output

For each query, print the corresponding result in a single line. In particular, for the queries K-TH, if k is larger than the number of elements in S, print the word 'invalid'.

Example

Input

8

I -1

I -1

I 2

C 0

K 2

D -1

K 1

K 2

Output

1

2

2

invalid

#include<cstdio>

#include<ext/pb_ds/assoc_container.hpp>

//pb_ds库这次内置了红黑树（red-black tree）、伸展树（splay tree）和排序向量树（ordered-vector tree，没找到通用译名，故自行翻译）。

//这些封装好的树都支持插入（insert）、删除（erase）、求kth（find_by_order）、求rank（order_of_key）操作，O(logn)内完成

using namespace std;

using namespace __gnu_pbds;

int read(){

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

tree<int,null_mapped_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>bbt;

//SPOJG++版本稍旧(4.3.2),需要写成null_mapped_type才可以(高级版本可以写null_type)

char in(){

    for(char ch=getchar();;ch=getchar()) if(ch>='A'&&ch<='Z') return ch;

}

int main(){

    char c;int x;

    for(int T=read();T--;){

        c=in();x=read();

        if(c=='I'){

            bbt.insert(x);

        }

        else if(c=='D'){

            bbt.erase(x);

        }

        else if(c=='K'){

            if(x<=bbt.size())

                printf("%d\n",*bbt.find_by_order(x-));

            else

                puts("invalid");

        }

        else{

            printf("%d\n",bbt.order_of_key(x));

        }

    }

    return ;

}

#include<cstdio>

#include<ext/pb_ds/assoc_container.hpp>

#include<ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("02")

using namespace std;

using namespace __gnu_pbds;

typedef long long ll;

ll read(){

    ll x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

typedef __gnu_pbds::tree<ll,null_mapped_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> T;

T bbt;ll ans;

int main(){

    ll n=read();

    for(ll i=,o,k;i<=n;i++){

        o=read();k=read();

        if(o==) bbt.insert((k<<)+i);else

        if(o==) bbt.erase(bbt.lower_bound(k<<));else

        if(o==) printf("%d\n",bbt.order_of_key(k<<)+);else

        {

            if(o==) ans=*bbt.find_by_order(k-);else

            if(o==) ans=*--bbt.lower_bound(k<<);else

            if(o==) ans=*bbt.lower_bound((k+)<<);

            printf("%lld\n",ans>>);

        }

    }

    return ;

}