Statement

In the Elden Ring, there's a well-known landmark called the "Royal City Sewers." This complex structure is a must-see for many experienced soul Ass and novice tarnished. It consists of $n$ rooms and a number of two-way corridors. Each room has up to three doors, and corridors lead from behind the room doors to other rooms. All corridors in each room lead to different rooms. The entire sewer is interconnected, meaning you can travel between any two rooms, though you may need to pass through other rooms.

You need help labeling the doors to make exploration easier. The idea is that if a room $u$ has $d_u$ doors leading to other rooms, these doors will be labeled $1, 2, \cdots, d_u$, and then all players will follow a simple procedure. If they are in room $u$ at the start of their exploration, they will choose the door labeled 1 and go through the corresponding corridor. If they are in room $u$ and enter from the corridor through a door labeled $i$, they will choose the door labeled with the next number (i.e., $i + 1$ if $i < d_u$, or 1 if $i = d_u$) and go through the corresponding corridor.

Now that we have the labeling set, you need to find the number of different corridors that the players will go through if they start their exploration from each room, assuming they follow the rules and walk long enough.

Input

Input a single integer $n$ in the first line, satisfying $1\leqslant n\leqslant 2\times 10^5$, representing the number of complex numbers.

In the following $n$ lines, each line contains two integers $a_i, b_i$ representing a complex number, where $-1\times 10^9 \leqslant a_i, b_i \leqslant 1\times 10^9$.

Output

Output two non-negative integers representing the values of $x$ and $y$ modulo 998244353, respectively.

Samples

3
1 1
4 5
1 4

998244316 5

5
114514 1919810
114 514
1 1
4 5
1 4

699025846 827685096

Notes

The figure below shows the player's path starting from node 1. The numbers marked on the dark blue and light blue arrows indicate the player's path in step $i$. This shows that the player passes through five different corridors.