Election Simulation in Autumn Country

The autumn country has n citizens numbered from 1 to n. Initially, each citizen votes for the candidate whose number is the same as their own. There are m rounds of pre-selection. In each round, a segment of citizens with indices in the range \([l_i, r_i]\) participates in a local pre-election. In this round, if a candidate obtains strictly more than half of the votes in the segment (i.e. more than \( \frac{r_i - l_i + 1}{2}\) votes), that candidate wins the round; otherwise, Xiao C arbitrarily chooses a winner (this candidate can be any candidate, not necessarily within the segment).

After announcing the winner of the round, exactly \(k_i\) citizens (selected deterministically as the earliest citizens whose current vote is not already for the round winner) change their vote to that candidate. After all rounds have concluded, the candidate with the highest number of votes becomes the president. In the event of a tie, the candidate with the smallest number is chosen.

You are to simulate all the rounds. For each round, print the winner’s candidate number. Finally, print the candidate number of the final president.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of citizens and the number of rounds respectively.

Each of the next \(m\) lines contains four integers \(l\), \(r\), \(q\), and \(k\):

• \(l\) and \(r\) (with \(1 \leq l \leq r \leq n\)) indicate the range of citizens participating in the current round.
• \(q\) is the candidate number chosen by Xiao C if no candidate obtains a majority in that round.
• \(k\) is the number of citizens who will change their vote to the round's winner after the round.

outputFormat

Output \(m+1\) lines:

• The first \(m\) lines each contain the winning candidate's number for that round.
• The last line contains the candidate number of the final president.

sample

5 2
1 3 2 2
2 5 3 1

2
3
2