Description

秋之国共有 $n$ 个人，分别编号为 $1,2,…,n$，一开始每个人都投了一票，范围 $1 \sim n$，表示支持对应编号的人当总统。

共有 $m$ 次预选，每次选取编号 $[l_i,r_i]$ 内的选民展开小规模预选，在该区间内获得超过区间大小一半的票的人获胜。如果没有人获胜，则由小 C 钦定一位候选者获得此次预选的胜利（获胜者可以不在该区间内），每次预选的结果需要公布出来，并且每次会有 $k_i$ 个人决定将票改投向该次预选的获胜者。

全部预选结束后，公布最后成为总统的候选人。

Input Format

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

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

接下来 $m$ 行，每行先有四个整数，分别表示 $l_i,r_i,s_i,k_i$，$s_i$ 表示若此次预选无人胜选，视作编号为 $s_i$ 的人获得胜利，接下来 $k_i$ 个整数，分别表示决定改投的选民。

Output Format

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

5 4
1 2 3 4 5
1 2 1 1 3
5 5 1 2 2 4
2 4 2 0
3 4 2 1 4

1
5
5
2
-1

Hint

对于前 $20 \%$ 的数据，$1 \leq n,m \leq 5000$。

对于前 $40 \%$ 的数据，$1 \leq n,m \leq 50000$，$\sum k_i \leq 50000$。

对于前 $50 \%$ 的数据，$1 \leq n,m \leq {10}^5$，$\sum k_i \leq 2 \times {10}^5$。

对于数据点 6~7，保证所有选票始终在 $1 \sim 10$ 之间。

对于 $100 \%$ 的数据，$1 \leq n,m \leq 5 \times {10}^5$，$\sum k_i \leq 10^6$，$1 \leq l_i \leq r_i \leq n$，$1 \leq s_i \leq n$。