Rahat inəklər (Gümüş)

Fermer Nxoinin Otlağı böyük bir 2D hüceyrə şəbəkəsi (şahmat taxtası) kimi təsəvvür edilə bilər. Əvvəlcə otlaq boşdur.

FN otlağa bir-bir n inək əlavə edəcək. i-ci inək (x[i], y[i]) hüceyrəsini tutacaq, bu hüceyrə digər inəklərin tutduğu hüceyrələrdən fərqlidir.

Bir inək "rahat" adlanır, əgər onun üfüqi və şaquli olaraq tam üç qonşusu varsa. Rahat inəklər daha az süd verir, buna görə də FN rahat inəklər olmayana qədər inəkləri əlavə etmək istəyir (əlavə edəcəyi inək də daxil olmaqla). Qeyd edək ki, əlavə edilən inəklərin x və y koordinatları mütləq 0..1000 intervalında olmalıdır.

Hər bir i üçün 1..n intervalında, yalnız 1..i inəklərin otlaqda olduğunu nəzərə alaraq, rahat inəklər qalmaması üçün FN-in əlavə etməli olduğu minimum inək sayını göstərin.

Giriş Məlumatları

Birinci sətir tam ədəd n (1 ≤ n ≤ 10^5) ehtiva edir. Növbəti n sətirin hər biri inəyin hüceyrə koordinatlarını göstərən 2 tam ədəd (x, y) (0 ≤ x, y ≤ 1000) ehtiva edir.

Çıxış Məlumatları

Hər bir i üçün 1..n intervalında, FN-in əlavə etməli olduğu minimum inək sayını ayrı-ayrı sətirlərdə göstərin.

Nümunə

i = 4 üçün, FN inəyi (2, 1) mövqeyinə əlavə etməlidir ki, (1, 1) mövqeyindəki inək rahat olmasın.

i = 9 üçün, FN-in edə biləcəyi ən yaxşı şey inəkləri (2, 0), (3, 0), (2, −1), (2, 3) mövqelərinə əlavə etməkdir.