题目背景

在World Final世界总决赛刚开始时，每个队伍都会开始看不同的题，而在比赛中如果获得一道题的首A(首支$\textbf{\color{green}{AC}}$该题的队伍)，会获得一个特殊的气球。

现在Jiangly想知道每道题的首A都被哪个队伍拿到了。

题目描述

已知这场比赛中有$n$道题目，编号为$1$到$n$。

Jiangly从$\texttt{DOMJudge}$服务器后台获得了提交数据，因为他只需要知道过题顺序，因此他只关心$\textbf{\color{green}{AC}}提交$。

现在按照时间顺序给出赛时所有的$\textbf{\color{green}{AC}}提交$，请你给出每道题第一个通过的队伍编号。

题目格式

输入格式

第一行输入两个整数 $n,q(1 \le n, q \le 10^6)$ ，分别表示题目数和$\textbf{\color{green}{AC}}$提交数。

接下来 $q$ 行，第 $i$ 行输入两个整数 $a_i,x_i(1 \le a_i \le 10^9,1 \le x_i \le n)$ ，表示编号为 $a_i$ 的队伍通过了第 $x_i$ 题，给出的顺序为时间顺序。

输出格式

输出 $n$ 行，第 $i$ 行输出一个整数 $b_i$ ，表示第一支通过第 $i$ 题的队伍编号，若该题没有队伍通过，则输出NaN。

题目样例

11 10
1 10
2 9
3 8
4 7
5 6
6 5
7 4
8 3
9 2
10 1

10
9
8
7
6
5
4
3
2
1
NaN

题目声明

本故事纯属虚构，灵感取材自2020 ICPC银川站