Falling Multiset

Input

The first line contains one integer $n$ (1 \le n \le 10^{5}) — the number of time units.

Each of the next $n$ lines contains two integers w_i and v_i (1 \le w_i \le n;1 \le v_i \le 10^{9}) — the weight and value of the item inserted at time $i$.

Output

For each time unit, print the sum of values of all items in the multiset modulo $998244353$.

Examples

Note

For the sample test case, the process will unfold as follows:

Time unit $1$: add $(4,3)$.

Update all items:

• $(4,3)$ becomes (3, 3 \cdot 4) = (3,12).

Sum of values: $12$.

Time unit $2$: add $(1,2)$.

Multiset before update: \{(3,12),(1,2)\}.

Update all items:

• $(3,12)$ becomes (2, 12 \cdot 3) = (2,36).

• $(1,2)$ becomes (0, 2 \cdot 1) = (0,2).

Sum of values: 36 + 2 = 38.

Time unit $3$: add $(3,3)$.

Multiset before update: \{(2,36),(0,2),(3,3)\}.

Update all items:

• $(2,36)$ becomes (1, 36 \cdot 2) = (1,72).

• $(0,2)$ stays $(0,2)$.

• $(3,3)$ becomes (2, 3 \cdot 3) = (2,9).

Sum of values: 72 + 2 + 9 = 83.

Time unit $4$: add $(2,1)$.

Multiset before update: \{(1,72),(0,2),(2,9),(2,1)\}.

Update all items:

• $(1,72)$ becomes (0, 72 \cdot 1) = (0,72).

• $(0,2)$ stays $(0,2)$.

• $(2,9)$ becomes (1, 9 \cdot 2) = (1,18).

• $(2,1)$ becomes (1, 1 \cdot 2) = (1,2).

Sum of values: 72 + 2 + 18 + 2 = 94.

Scoring

1. Subtask $1$ ($20$ points): (n \le 10^{4})

2. Subtask $2$ ($30$ points): (w_i \le 10^4 for all 1 \le i \le n)

3. Subtask $3$ ($50$ points): (w_1 = w_2 = \cdots = w_n)

4. Subtask $4$ ($50$ points): (n \le 5 \cdot 10^{4})

5. Subtask $5$ ($450$ points): No additional constraints