Sıyıq

Fermer Conun inəkləri səhər yeməyində yalnız dənli bitkiləri sevirlər! Əslində, inəklərin iştahı o qədər böyükdür ki, hər biri bir oturuşda bütün bir qutu dənli bitki yeyir.

Son zamanlarda təsərrüfata $m$ fərqli növ dənli bitki partiyası gəlib.

Təəssüf ki, hər dənli bitkinin yalnız bir qutusu var! Hər bir $n$ inəyin sevimli və ikinci sevimli dənli bitkisi var. İnəklər dənli bitkiləri seçərkən aşağıdakı prosesi izləyirlər:

• Əgər sevimli dənli bitkisinin qutusu hələ də mövcuddursa, onu götürür və gedir.

• Əks halda, əgər ikinci sevimli dənli bitkisinin qutusu hələ də mövcuddursa, onu götürür və gedir.

• Əks halda, məyus halda heç nə götürmədən gedir.

İnəklər dənli bitkilər üçün sıraya düzülüb. Hər bir $i(0\le i\le n-1)$ dəyəri üçün, fermer Con sıranın əvvəlindən ilk $i$ inəyi çıxarsa, neçə inəyin dənli bitki qutusu götürəcəyini müəyyən edin.

Giriş verilənləri

Birinci sətir iki tam ədəd $n(1\le n\le 10^5)$ və $m(1\le m\le 10^5)$ ehtiva edir. Hər bir $i(1\le i\le n)$-ci sətir iki tam ədəd $f_i$ və $s_i(1\le f_i,s_i\le m$ və $f_i\ne s_i)$ ehtiva edir, bu da növbədəki $i$-ci inəyin birinci və ikinci sevimli dənli bitkisini göstərir.

Çıxış verilənləri

Hər bir $i(0\le i\le n-1)$ dəyəri üçün, $i$ üçün cavabı ehtiva edən bir sətir çıxarın.

Nümunələr

Əgər ən azı iki inək qalarsa, onlardan ikisinə dəqiq bir qutu dənli bitki düşəcək.