Description

There are $n$ people in the State of Qiu, numbered $1, 2, \dots, n$. Initially, each person casts one vote in the range $1 \sim n$, indicating support for the person with that ID to become president.

There are $m$ primaries. In each primary, voters with indices $[l_i, r_i]$ are selected for a small-scale primary. Within that interval, the person who gets more than half of the votes in the interval wins. If no one wins, Xiao C designates a candidate with ID $s_i$ as the winner (the winner may be outside the interval). The result of each primary must be announced, and after each primary, $k_i$ people decide to switch their votes to the winner of that primary.

After all primaries end, announce the candidate who finally becomes president.

Input Format

The first line contains two integers $n, m$, the population of Qiu and the number of primaries.

The second line contains $n$ integers, representing the votes cast by voters numbered $1 \sim n$.

Then follow $m$ lines. Each line first contains four integers $l_i, r_i, s_i, k_i$, where $s_i$ means that if no one wins this primary, the person with ID $s_i$ is considered the winner. Then follow $k_i$ integers, representing the voters who decide to switch their votes.

Output Format

Output $m+1$ lines in total. The first $m$ lines represent the result of each primary. The last line represents the candidate who finally becomes president. If in the end no one still meets the winning condition, output $-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

For the first $20 \%$ of the testdata, $1 \leq n, m \leq 5000$.

For the first $40 \%$ of the testdata, $1 \leq n, m \leq 50000$, $\sum k_i \leq 50000$.

For the first $50 \%$ of the testdata, $1 \leq n, m \leq {10}^5$, $\sum k_i \leq 2 \times {10}^5$.

For data points 6~7, it is guaranteed that all votes always remain in $1 \sim 10$.

For $100 \%$ of the testdata, $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$.

Translated by ChatGPT 5