Description

小K学长正在匆匆的复习，但是不知不觉间进入了梦乡~

小K学长在这个梦中，穿越进了一个精灵世界，这个世界现在正在选举精灵王，总共有$n$只精灵，编号从$(1...n)$，现在共有$m$张票，对于第$i(1 \leq i \leq m)$票，会投给编号为$a_i$的精灵。

现在要求你仅考虑前$i$张票选举的结果，回答是哪位精灵会成为精灵王？

票数最多的成为精灵王，若有多个精灵票数相同，编号小的成为精灵王。

Format

Input

第一行两个正整数$n(1 \leq n \leq 10 ^ 9)$和$m(1 \leq m \leq 2 \times10^5)$, 表示精灵的数量和票数。

接下来输入$m$个数字$a_i(1 \leq a_i \leq n)$，表示投给精灵的编号。

Output

输出 $m$行，每行一个正整数表示可以成为精灵王的编号。

Samples

3 7
1 2 2 3 1 3 3

1
1
2
2
1
1
3

100 5
100 90 80 70 60

100
90
80
70
60

Hint