Bối cảnh: Quán trọ huyền thoại Zagrebian có tên là Kod Žnidaršića.

Thời gian: Năm 1936.

Tóm tắt cốt truyện: Franjo và bạn bè đang thảo luận về các sự kiện hiện tại ở Abyssinia trong khi thưởng thức một vài ly rượu tại quầy bar. Con trai của ông, bé Perica, đang ngồi ở một bàn nhỏ trong góc của quán bar. Trước mặt Perica có ~N~ chiếc ly được đánh số từ ~1~ đến ~N~. Thể tích (tính bằng nanolit) của mỗi ly đã biết cũng như lượng chất lỏng hiện đang có bên trong nó.

Vấn đề: Bé Perica muốn biết số lượng ly lớn nhất có thể làm rỗng bằng cách đổ chất lỏng giữa các ly. Bé có thể tự do đổ bất kỳ số lượng nanolit nào từ một ly này sang ly khác, bao nhiêu lần tùy ý, miễn là không làm tràn chất lỏng ra ngoài.

Nhiệm vụ của bạn là xuất ra số lượng ly rỗng cùng với một cấu hình chất lỏng có thể có trong tất cả các ly. Nếu có nhiều cấu hình cho ra cùng số lượng ly rỗng, hãy xuất bất kỳ một trong số đó. Lưu ý rằng không cần thiết phải giảm thiểu số lần đổ chất lỏng giữa hai ly.

Input

• Dòng đầu tiên chứa một số nguyên ~N~ ~(1 \leq N \leq 1000)~ từ mô tả bài toán.
• Mỗi dòng tiếp theo trong số ~N~ dòng chứa hai số nguyên ~T_i~ ~(0 \leq T_i \leq 10^9)~ và ~Z_i~ ~(1 \leq Z_i \leq 10^9)~ lần lượt đại diện cho lượng chất lỏng hiện tại trong ly thứ ~i~ và thể tích của nó. Cả hai giá trị đều được cho bằng nanolit và lượng chất lỏng hiện tại không được lớn hơn thể tích của ly, tức là ~T_i \leq Z_i~.

Output

• Trong dòng đầu tiên, bạn nên xuất ra số lượng ly rỗng lớn nhất có thể bằng cách đổ chất lỏng giữa các ly.
• Trong dòng thứ hai, bạn nên xuất ra lượng chất lỏng trong mỗi ly sau khi Perica đã thực hiện các lần đổ cần thiết. Các ly nên được sắp xếp theo thứ tự từ ly số ~1~ đến ly số ~N~.

Chú thích

• Dòng đầu tiên viết đúng được 4 điểm, và mỗi dòng thứ hai viết đúng được 1 điểm cho mỗi trường hợp kiểm tra.
• Trong các trường hợp kiểm tra có tổng cộng 20 điểm, tất cả các ly sẽ có cùng thể tích.

Sample Input 1

5
2 6
1 6
0 6
6 6
5 6

Sample Ouput 1

2
6 6 2 0 0

Sample Input 2

5
4 5
2 7
5 5
0 10
7 9

Sample Ouput 2

3
0 0 0 10 8

Sample Input 3

8
2 6
3 4
1 1
9 10
0 10
4 5
6 8
3 9

Sample Ouput 3

5
0 0 0 9 10 0 0 9

Giải thích

Làm rõ ví dụ thứ hai: Một trong những cấu hình đổ chất lỏng có thể là như sau:

1. đổ toàn bộ từ ly 1 vào ly 2.
2. đổ toàn bộ từ ly 2 vào ly 4.
3. đổ bốn nanolit từ ly 3 vào ly 4.
4. đổ một nanolit từ ly 3 vào ly 5. Các ly số 1, 2 và 3 bây giờ đã rỗng.