يريد Jeongol تخزين صناديق في مستودع. يوجد $N$ صندوقًا مرقمًا من $1$ إلى $N$. حجم الصندوق $i$ ($1\le i\le N$) هو $s_i$ وسعته التخزينية $c_i$. سعة كل صندوق أصغر من حجمه، أي $c_i<s_i$.

يرى Jeongol أن كثرة الصناديق تجعل المستودع مزدحمًا، ويريد وضع صناديق داخل صناديق أخرى. يجب تحقيق الشروط التالية:

• يمكن للصندوق احتواء صندوق لا يتجاوز حجمه سعته التخزينية.

• يمكن وضع صندوق يحتوي بالفعل على صندوق آخر داخل صندوق آخر أيضًا.

• يمكن لكل صندوق أن يحتوي مباشرة على صندوق واحد على الأكثر. أي يمكن وضع صندوق آخر واحد على الأكثر داخله، لكن يسمح بأن يحتوي ذلك الصندوق بدوره على صناديق أخرى.

تكلفة التخزين هي عدد الصناديق التي لا توجد داخل أي صندوق آخر.

مثلًا، اعتبر $N=4$ والأحجام والسعات في الجدول التالي:

إذا وضع الصندوق 4 داخل الصندوق 1، والصندوق 1 داخل الصندوق 3 كما في الشكل أدناه، يكون هناك صندوقان غير محتويين داخل غيرهما، فتكون تكلفة التخزين 2.

لكن وضع الصندوقين 2 و4 داخل الصندوق 3 كما في الشكل التالي يخالف الشروط، لأن الصندوق 3 يحتوي مباشرة على صندوقين.

ليس من الضروري إبقاء جميع الصناديق في المستودع. يخطط Jeongol للاحتفاظ ببعض الصناديق ذات الأرقام الأصغر فقط والتخلص من الباقي. لم يقرر بعد عدد الصناديق التي سيستخدمها.

ساعد Jeongol بكتابة برنامج يحسب، لكل $i$ من $1$ إلى $N$، أقل تكلفة لتخزين الصناديق $1,2,\ldots,i$.

القيود

• جميع الأعداد المعطاة صحيحة.
• $2\le N\le2\times10^5$.
• $1\le c_i<s_i\le10^9$ ($1\le i\le N$).

المهام الفرعية

1. (7 نقاط) $N\le6$.
2. (12 نقاط) $s_i=c_i+1$.
3. (26 نقاط) $N\le1000$.
4. (17 نقاط) $s_i\le100$.
5. (38 نقاط) لا قيود إضافية.

الإدخال

يحتوي السطر الأول على عدد الصناديق $N$.

تصف الأسطر $N$ التالية، بدءًا من السطر الثاني، الصناديق. يحتوي السطر $i$ منها على حجم الصندوق $i$، أي $s_i$، وسعته $c_i$، مفصولين بمسافة.

الإخراج

اطبع $N$ أسطر.

في السطر $i$ ($1\le i\le N$)، اطبع أقل تكلفة لتخزين الصناديق $1,2,\ldots,i$.

أمثلة

الإدخال 1

4
6 4
5 1
9 8
2 1

الإخراج 1

1
2
2
2

الإدخال 2

6
3 2
5 4
3 2
4 3
4 3
3 2

الإخراج 2

1
1
2
2
2
3

الإدخال 3

8
13 6
7 5
9 4
11 10
4 2
15 5
16 7
8 3

الإخراج 3

1
2
3
3
3
4
4
5