The Sphinx has prepared a riddle for you.

The Sphinx holds a multiset $\operatorname{A}$ that does not contain zero. The sums of the $2^{|A|}$ subsets of $\operatorname{A}$ form a multiset $\operatorname{B}$, which can be decomposed into several pairs $(x_i, y_i)$, where $x_i$ is an element and $y_i$ is its frequency.

The mischievous Sphinx has only given you the final pairs $(x_i, y_i)$.

As a clever person, you notice that there may be many distinct multisets $\operatorname{A}$ that can be reconstructed from the given information. You want to find the number of distinct multisets $\operatorname{A}$ that can be reconstructed, modulo $998244353$, and the lexicographically smallest such $\operatorname{A}$.

It is guaranteed that for the given $(x_i, y_i)$, there exists at least one valid $\operatorname{A}$.

Two multisets $\operatorname{A}$ and $\operatorname{B}$ are considered distinct if and only if there exists an element whose frequency in $\operatorname{A}$ is different from its frequency in $\operatorname{B}$.

Input

The first line contains a positive integer $n$, representing the number of pairs.

The next $n$ lines each contain two integers $x_i$ and $y_i$, representing the given pairs.

Output

The first line outputs the number of distinct valid multisets $\operatorname{A}$ modulo $998244353$.

The second line outputs an integer $n$, representing the length of the lexicographically smallest $\operatorname{A}$.

The third line outputs $n$ integers, representing the contents of the lexicographically smallest $\operatorname{A}$. The elements should be output in non-decreasing order. The lexicographical comparison of two sets is defined as the lexicographical comparison of the sequences formed by sorting their elements in non-decreasing order.

Note: If you output the correct value for the first line for all test cases, you will receive $25\%$ of the points for that test case. However, even if you only aim for this partial credit, your output format must be valid. If the first line is incorrect, no points will be awarded.

Examples

Input 1

3
0 1
1 2
2 1

Output 1

1
2
1 1

Input 2

5
-2 1
-1 2
0 2
1 2
2 1

Output 2

2
3
-2 1 1

Note

For Example 1, the valid $\operatorname{A}$ is $\{1, 1\}$.

For Example 2, the valid $\operatorname{A}$ are $\{-2, 1, 1\}$ or $\{-1, -1, 2\}$.

Constraints

For all data, it is guaranteed that $1 \leq n \leq 10^5$, $-10^{13} \leq x_i \leq 10^{13}$, $1 \leq y_i \leq 10^{13}$, and all $x_i$ are distinct.

This problem has $4$ subtasks. The score for a subtask is the minimum score of the test cases within it.