Given the distinct nature of the two problems provided in the source document, they are translated separately below.

Problem 1: Fish

Given $n$ distinct integer points (points where both the $x$ and $y$ coordinates are integers) in a Cartesian coordinate system, we define an ordered 6-tuple of points $\langle A, B, C, D, E, F \rangle$ chosen from these $n$ points as a "fish" if and only if: $AB = AC$, $BD = CD$, $DE = DF$ (for symmetry), and $\angle BAD, \angle CAD$ as well as $\angle EDA, \angle FDA$ are all acute angles (the head and the tail cannot be concave), while $\angle BDC, \angle EDF > 90^\circ$ (i.e., they are obtuse or straight angles, so the tail does not look awkward).

The following figure is an example of a valid fish:

Fish with the same set of points but different orderings are considered distinct. That is, $\langle A, B, C, D, E, F \rangle$ and $\langle A, C, B, D, E, F \rangle$ are considered different fish (as a fish has a back and a belly side). Similarly, $\langle A, B, C, D, E, F \rangle$ and $\langle A, B, C, D, F, E \rangle$ are also considered different fish (assuming the fish tail can be tied in a knot).

Calculate how many fish can be formed from the given $n$ points. The data guarantees that the $n$ points are distinct.

Input

The input file is named fish.in. The first line contains a positive integer $n$, representing the number of points on the plane. The next $n$ lines each contain two integers $x, y$, representing the coordinates of the points.

Output

The output file is named fish.out. Output a single non-negative integer representing the number of fish.

Constraints

• For the first 20% of the data, $n \le 10$, $0 \le |x|, |y| \le 5$.
• For the first 40% of the data, $n \le 300$, $0 \le |x|, |y| \le 10^5$.
• For another 20% of the data, $|x|, |y| \le 20$.
• For all data, $6 \le n \le 1000$, $0 \le |x|, |y| \le 10^9$, and all $n$ points are distinct.

Examples

Input 1

8
-2 0
-1 0
0 1
0 -1
1 0
2 0
3 1
3 -1

Output 1

16

Problem 2: JOJO

JoJo's Bizarre Adventure is a very popular manga. The protagonist often likes to shout "Ora" or "Muda" repeatedly. To prevent too much text from obscuring the manga content, the new manga will use $x$ Ora or $x$ Muda to represent $x$ occurrences of "Ora" or "Muda".

To simplify the content, we use letters to represent the shouted words. We use numbers and letters to represent a string, for example: 2 a 3 b represents the string aabbb.

Initially, the manga contains no text. You need to perform $n$ operations in sequence. There are only two types of operations:

1. 1 x c: Add $x$ occurrences of character $c$ to the current string (append $x$ characters $c$ to the end of the current string). It is guaranteed that the current string is empty or the last character of the string is not $c$.
2. 2 x: Restore the manga to the state after the $x$-th operation. If $x=0$, the string becomes empty. If the current string is bbaabbb and the string after the 4th operation was bb, then 2 4 will change bbaabbb to bb. It is guaranteed that $x$ is less than the current operation count.

Jotaro Kujo is very clever. Now that Dio has been defeated, he has started to consider some problems regarding his manga: For every prefix $A$ of a string, there exists a longest prefix $B$ (shorter than $A$) that matches a suffix of $A$. Let the length of this longest prefix $B$ be $L$. If $L=0$, it means $B$ is an empty string.

After each operation, you need to calculate the sum of $L$ for all prefixes of the current string, modulo $998244353$, and output the result to compare with the answer calculated by Star Platinum.

For example, the $L$ values for bbaaabba are: 0 1 0 0 0 1 2 3, so the answer for this string is $7$.

Input

The input file is named jojo.in. The first line contains a positive integer $n$, representing the number of operations. The next $n$ lines each contain an operation in the format described above, for example: 1 x c 2 x The data is guaranteed to be valid.

Output

Output $n$ lines, each containing the sum of $L$ values modulo $998244353$ after each operation.