Năm 1936, tại Kod Žnidaršića, nơi dừng chân huyền thoại của thủ đô Zagreb. Fanjo và những người bạn đang tận hưởng đồ uống của mình và bàn về những sự kiện ở Abyssinia. Con trai Fanjo, Percia, đang ngồi trong góc của quán. Trước mặt Percia là ~N~ cái ly được đánh số từ ~1~ tới ~N~. Với mỗi ly, chúng ta biết được thể tích của ly và thể tích của lượng chất lỏng có trong ly (đều có đơn vị là nano-lít).

Percia muốn biết số lượng ly lớn nhất mà cậu ấy có thể làm cho nó cạn bằng cách đổ lượng chất lỏng giữa các ly với nhau. Cậu ấy có thể đổ tùy ý một số nguyên nano-lít chất lỏng sang các ly khác. Cậu ấy có thể làm nhiều lần tùy ý miễn sao ly không tràn.

Bạn hãy tính số lượng ly tối đa có thể làm cạn và trạng thái cuối cùng của các ly sau khi đổ xong. Nếu có nhiều trạng thái thỏa, in ra 1 trong số chúng.

Lưu ý: bạn không cần tối thiểu số lần đổ chất lỏng từ ly này sang ly khác.

Input

Dòng đầu tiên gồm 1 số nguyên ~N (1 \leq N \leq 1000)~.

~N~ dòng tiếp theo mỗi dòng gồm 2 số nguyên ~T_i~ ~(0 \leq T_i \leq 10^9)~ và ~Z_i~ ~(0 \leq Z_i \leq 10^9)~ lần lượt là lượng chất lỏng đang chứa và thể tích của ly thứ ~i~. Cả 2 đều có đơn vị là nano-lít và lượng chất lỏng đang chứa không thể nhiều hơn thể tích của ly ~(T_i \leq Z_i)~

Output

Dòng đầu tiên là số lượng ly lớn nhất có thể làm cạn.

Dòng thứ 2 là lượng chất lỏng của từng ly sau khi đổ xong theo thứ tự từ ~1~ tới ~N~

Sample Input 1

5
2 6
1 6
0 6
6 6
5 6

Sample Output 1

2
6 6 2 0 0

Sample Input 2

5
4 5
2 7
5 5
0 10
7 9

Sample Output 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 Output 3

5
0 0 0 9 10 0 0 9

Giải thích

Ở ví dụ 2 ta có thể làm như sau:

1. Đổ tất cả từ ly 1 sang ly 2.
2. Đổ tất cả từ ly 2 sang ly 4.
3. Đổ 4 nano-lít chất lỏng từ ly 3 sang ly 4.
4. Đổ 1 nano-lít chất lỏng từ ly 3 sang ly 5.

Ràng buộc

• ~4~ test đầu tất cả các ly đều có cùng thể tích
• ~6~ test còn lại không ràng buộc gì thêm