Коровы фермера Джона не любят ничего, кроме хлопьев на завтрак! Фактически, у коров такой большой аппетит, что каждая из них съедает целую коробку хлопьев за один прием пищи. Недавно в хозяйство поступила партия зерновых $m$ разных сортов. К сожалению, у каждой крупы есть только одна коробка! У каждой из $n$ коров есть любимая каша и вторая любимая каша. Когда корова совершает выбор злаков, она выполняет следующий процесс: \begin{itemize} \item Если коробка с ее любимыми хлопьями все еще доступна, она берет ее и уходит. \item В противном случае, если коробка ее второй любимой каши все еще доступна, она берет ее и уходит. \item Иначе она разочарованно мычит и уходит, не взяв каши. \end{itemize} Коровы выстроились в очередь за хлопьями. Для каждого значения $i~(0 \le i \le n − 1)$ определите, сколько коров возьмет коробку хлопьев, если фермер Джон уберет первые $i$ коров с линии. \InputFile Первая строка содержит два целых числа $n~(1 \le n \le 10^5)$ и $m~(1 \le m \le 10^5)$. Для каждого значения $i~(1 \le i \le n)~i$ - ая строка содержит два целых числа $f_i$ и $s_i~(1 \le f_i, s_i \le m$ и $f_i \ne s_i)$, обозначающие первую и вторую по популярности крупу $i$-ой коровы в очереди. \OutputFile Для каждого значения $i~(0 \le i \le n − 1)$ выведите строку, содержащую ответ для $i$. \Examples Если останется хотя бы две коровы, то ровно двум из них достанется ящик каши.