黑恶势力的反攻计划被小C成功摧毁，黑恶势力只好投降。秋之国的人民解放了，举国欢庆。此时，原秋之国总统因没能守护好国土，申请辞职，并请秋之国人民的大救星小C钦定下一任。作为一名民主人士，小C决定举行全民大选来决定下一任。为了使最后成为总统的人得到绝大多数人认同，小C认为，一个人必须获得超过全部人总数的一半的票数才能成为总统。如果不存在符合条件的候选人，小C只好自己来当临时大总统。为了尽可能避免这种情况，小C决定先进行几次小规模预选，根据预选的情况，选民可以重新决定自己选票的去向。由于秋之国人数较多，统计投票结果和选票变更也成为了麻烦的事情，小C找到了你，让你帮他解决这个问题。

【问题描述】秋之国共有n个人，分别编号为1,2,…,n，一开始每个人都投了一票，范围1~n，表示支持对应编号的人当总统。共有m次预选，每次选取编号[li,ri]内的选民展开小规模预选，在该区间内获得超过区间大小一半的票的人获胜，如果没有人获胜，则由小C钦定一位候选者获得此次预选的胜利（获胜者可以不在该区间内），每次预选的结果需要公布出来，并且每次会有ki个人决定将票改投向该次预选的获胜者。全部预选结束后，公布最后成为总统的候选人

第一行两个整数n,m，表示秋之国人数和预选次数。

第二行n个整数，分别表示编号1~n的选民投的票。

接下来m行，每行先有4个整数，分别表示li,ri,si,ki，si表示若此次预选无人胜选，视作编号为si的人获得胜利

接下来ki个整数，分别表示决定改投的选民。

1<=n,m<=500,000，Σki<=1,000,000，1<=li<=ri<=n，1<=si<=n。

共m+1行，前m行表示各次预选的结果，最后一行表示最后成为总统的候选人，若最后仍无人胜选，输出-1。

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#define N 500010

#define lson l , mid , a[x].ls

#define rson mid + 1 , r , a[x].rs

using namespace std;

struct data

{

	int ls , rs , si;

}a[N * 60];

int w[N] , root[N] , tot;

inline int read()

{

    int ret = 0; char ch = getchar();

    while(ch < '0' || ch > '9') ch = getchar();

    while(ch >= '0' && ch <= '9') ret = ret * 10 + ch - '0' , ch = getchar();

    return ret;

}

void update(int p , int v  , int l , int r , int &x)

{

    if(!x) x = ++tot;

    a[x].si += v;

    if(l == r) return;

    int mid = (l + r) >> 1;

    if(p <= mid) update(p , v , lson);

    else update(p , v , rson);

}

int query(int b , int e , int l , int r , int x)

{

    if(!x) return 0;

    if(b <= l && r <= e) return a[x].si;

    int mid = (l + r) >> 1 , ans = 0;

    if(b <= mid) ans += query(b , e , lson);

    if(e > mid) ans += query(b , e , rson);

    return ans;

}

int main()

{

    srand(2333666);

    int n , m , i , l , r , s , k , x , p , t;

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

    for(i = 1 ; i <= n ; i ++ ) w[i] = read() , update(i , 1 , 1 , n , root[w[i]]);

    while(m -- )

    {

        l = read() , r = read() , s = read() , k = read() , p = 0;

        for(i = 1 ; i <= 15 ; i ++ )

        {

            t = w[rand() % (r - l + 1) + l];

            if(query(l , r , 1 , n , root[t]) > (r - l + 1) >> 1)

            {

                p = t;

                break;

            }

        }

        if(!p) p = s;

        printf("%d\n" , p);

        for(i = 1 ; i <= k ; i ++ ) x = read() , update(x , -1 , 1 , n , root[w[x]]) , update(x , 1 , 1 , n , root[p]) , w[x] = p;

    }

    p = -1;

    for(i = 1 ; i <= 15 ; i ++ )

    {

        t = w[rand() % n + 1];

        if(a[root[t]].si > n >> 1)

        {

            p = t;

            break;

        }

    }

    printf("%d\n" , p);

    return 0;

}