void find(int l,int r){    if (l>r || a[l]>x || a[r]<x) return;    int mid = (l+r) >> 1;    if (a[mid] == x){        if (mid < pos)pos=mid;        if (a[mid-1] == x) find(l, mid-1);        if (a[mid+1] == x) find(mid+1, r);        return;    }    if (x > a[mid]) find(mid+1, r);    else find(l, mid-1);}

bool is_prime(int x){    if (x <= 1) return 0;    for (int i = 2; i <= floor(sqrt(x)+0.5); i++){        if (x % i == 0) return 0;    }    return 1;}

for (int i = 1; i <= n; i++){    if (!flag[i]) ans[tot++]=i;    for (int j=0 ; j < tot && i*ans[j] <= n ;j++){        flag[i * ans[j]]=1;        if (i % ans[j]==0) break;    }}

void merge(int a, int m, int b, int n){    int i = a, j = b, k = a;    while (i <= m && j <= n){        if (s[i] <= s[j]) t[k++] = s[i++];        else{            t[k++] = s[j++];            ans += m-i+1;        }    }    while (i <= m) t[k++] = s[i++];    while (j <= n) t[k++] = s[j++];    for (int i=a; i<=n; i++) s[i] = t[i];}void mergesort(int a, int b){    if (a == b) return;    int mid = (a+b) / 2;    mergesort(a, mid);    mergesort(mid+1, b);    merge(a, mid, mid+1, b);}//ans为逆序对个数

void shift_down(int p){    int mp = 2*p;    while (mp <= n){        if (p*2 == n || a[p*2] < a[p*2+1]) mp=2*p; else mp=2*p+1;        if (a[mp] < a[p]) swap(a[mp], a[p]); else break;        p=mp; mp=2*p;    }}void shift_up(int p){    while (p > 1 && a[p] < a[p/2]){        swap(a[p], a[p/2]);        p /= 2;    }}

int find(int x){return (x==f[x]) ? x : f[x] = find(f[x]); }int union(int a, int b){    int x=find(a), y=find(b);    if (rank[a]<rank[b]) father[a]=b;    else{        father[b]=a; if (rank[b]==rank[a])++rank[b];    }}

struct node{int l, r, cover; };void bulid_tree(int p, int s, int t){    node &a=tree[p];    a.l = s; a.r = t;    if (a.l == a.r) return;    int mid = (s+t) >> 1;    bulid_tree(p*2, s, mid);    bulid_tree(p*2+1, mid+1, t);}void insert(int p, int s, int t){    node &a = tree[p];    if (a.l == s && a.r == t) {a.cover++; return;}    if (a.l == a.r) return; //不能写成s==t    int mid = (a.l+a.r) >> 1;    if (t <= mid) insert(p*2, s, t);    else if (s > mid) insert(p*2+1, s, t);    else{        insert(p*2, s, mid);        insert(p*2+1, mid+1, t);    }} int count(int p, int x){    node &a = tree[p];    if (a.l == x && a.r == x) return a.cover;    int mid = (a.l+a.r) >> 1,t = 0;    if (x <= mid) t = count(p*2, x);    else t = count(p*2+1, x);    return (a.cover + t);}

#define lowbit(i) i&(-i)void update(int x, int y, int d){    x++; y++;    for (int i=x; i<INF; i+=lowbit(i))        for (int j=y; j<INF; j += lowbit(j))        c[i][j] += d;} int count(int x,int y){    int ans=0;    x++; y++;    for (int i=x;i;i-=lowbit(i))        for (int j=y;j;j-=lowbit(j))        ans+=c[i][j];    return ans;} 

struct Trie{    int tot,root,child[max_node][charset];    bool flag[max_node];    Trie()    {        memset(child[1],0,sizeof(child[1]));        flag[1]=0;        root=tot=1;    }void insert(const char *str) //刚传进来的时候*str表示的是str[0] str表示整个字符数组    {        int *cur=&root;        for (const char *p=str;*p;++p) //p刚开始指向str[0] ++p表示取str的下一位 若为‘\0‘则退出        {            cur=&child[*cur][*p-‘a‘];            if (*cur==0)            {                *cur=++tot;                memset(child[tot],0,sizeof(child[tot]));                flag[tot]=0;            }        }        flag[*cur]=1;    }    bool query(const char *str)    {        int *cur=&root;        for (const char *p=str;*p && *cur;++p)            cur=&child[*cur][*p-‘a‘];        return (*cur && flag[*cur]);    }};