Bessie là một con bò đói. Mỗi ngày, vào bữa tối, nếu trong chuồng có cỏ khô thì nó sẽ ăn một đống cỏ khô. Nông dân John không muốn Bessie chết đói, vì vậy vào một số ngày, ông ta gửi cỏ khô đến vào buổi sáng (trước bữa tối). Cụ thể, vào ngày \(d_i\), John sẽ gửi đến \(b_i\) đống cỏ khô (\(1 \leq d_i \leq 10^{14}\), \(0 \leq b_i \leq 10^{9}\) ).
Lần cập nhật \(U\) \((1 \leq U \leq 10^5)\) diễn ra như sau: Cho một cặp \((d,b)\), cho biết số lượng cỏ khô đến vào ngày \(d\) chuyển thành \(b\). Sau mỗi lần cập nhật, in ra tổng tất cả các ngày mà Bessie có ăn cỏ khô \(modulo\) \(10^9+7\).

Input

\(U\), theo sau là \(U\) dòng miêu tả các cập nhật.

Output

Tổng sau mỗi lần cập nhật \(modulo\) \(10^9+7\).

Scoring

• Subtask \(1\): \(U<=5000\)
• Subtask \(2\): Các lần cập nhật chỉ làm tăng số lượng cỏ khô tại ngày \(d\).
• Subtask \(3\): Không có điều kiện gì thêm.

Example

3
4 3
1 5
1 2 

15
36
18

9
1 89
30 7
101 26
1 24
5 1
60 4
5 10
101 0
1 200

4005
4656
7607
3482
3507
3753
4058
1107
24531