After the Land of Gnomes was freed from evil, Svetozar was unanimously elected as the administrator, who now has to decide how best to organize the defense against evil mages.
At the next general assembly, all gnomes lined up in a row. The gnome numbered $$$i$$$ in the row has a hat of color $$$a_i$$$ on their head. Svetozar wants to choose several consecutive gnomes for the Council of the Land of Gnomes. But if strictly more than half of the gnomes in the Council wear hats of the same color, they will form an absolute majority. Svetozar does not yet know what consequences an absolute majority might have, but he fears it in advance.
For now, Svetozar is only considering which gnomes to choose. From time to time, he asks you one of two types of questions:
The first line contains integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 2 \cdot 10^5$$$): the number of gnomes and the number of Svetozar's questions.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$): the colors of the gnomes' hats.
Then, $$$q$$$ questions follow, one per line, in one of the two formats described above:
For each question of the second type, print an integer: the color of the absolute majority for the given set of gnomes, or $$$-1$$$ if there is no such color.
6 101 1 2 3 4 42 1 42 1 32 2 52 5 61 3 12 1 32 3 61 6 12 1 62 4 5
-1 1 -1 4 1 -1 1 -1
After the questions of the first type, the hat colors of the gnomes will look like $$$(1, 1, 1, 3, 4, 4)$$$ and $$$(1, 1, 1, 3, 4, 1)$$$ respectively.