P3765 Presidential Election

The counterattack plan of the criminal forces was successfully crushed by Xiao C, and they had no choice but to surrender. The people of the State of Qiu were liberated, and the whole country celebrated. At this moment, the former president of Qiu, having failed to protect the nation, resigned and asked the great savior of the people, Xiao C, to designate the next president. As a democrat, Xiao C decided to hold a nationwide election to determine the next president. To ensure the final president is recognized by the vast majority, Xiao C believes that one must receive more than half of all votes to become president. If no candidate meets this condition, Xiao C will have to serve as the interim president himself. To minimize this possibility, Xiao C decided to hold several small-scale primaries first; based on the results of these primaries, voters may change their votes. Since Qiu has a large population, tallying votes and tracking changes became troublesome. Xiao C turned to you for help to solve this problem.

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.

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 $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$.

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