C. Curly Palindromes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$n$$$ points in the plane $$$(n \leq 100)$$$. All the points are distinct. Each point is labeled with a letter.

Find the largest curly palindrome.

A curly palindrome is a sequence such that:

  • for all $$$2 \leq i \leq \text{len}(q)-1$$$, the angle of the points $$$q_{i-1} q_i q_{i+1}$$$, is counterclockwise. Formally, let $$$\mathbf{u} = q_i - q_{i-1}$$$ and $$$\mathbf{v} = q_{i+1} - q_i$$$, then $$$\text{cross}(\mathbf{u}, \mathbf{v}) \gt 0$$$, $$$\text{cross}(\mathbf{a},\mathbf{b}) := \mathbf{a}_x \cdot \mathbf{b}_y - \mathbf{a}_y \cdot \mathbf{b}_x $$$.
  • No two adjacent points in the sequence should be equal, $$$q_i \neq q_{i+1}$$$. It is allowed to use the same point multiple times, as long as the occurrences are not adjacent.
  • Lastly, the labels on the points in the curly palindrome must spell out a palindrome.
If you can make curly palindromes of unbounded size, output "Infinity".
Input

The first line of input contains a single integer, $$$n$$$ ($$$1 \leq n \leq 100$$$)  — the number of points in the input.

Each of the next $$$n$$$ lines contains the description of a labeled point. Each line contains two integers $$$x$$$ and $$$y$$$ and a lowercase english character $$$c$$$, ($$$0 \leq x,y \leq 10^9$$$)  — the coordinates of the point and the label of the point.

Output

Print a single line containing the length of the largest curly palindrome of the labeled pointset. If the length can be unbounded, instead print on a single line the word "Infinity"

Examples
Input
4
0 0 o
1 1 c
2 2 p
3 3 c
Output
2
Input
3
2 3 e
3 2 e
8 9 e
Output
Infinity
Note

In the second case, palindromes of any length $$$k$$$ can be made, by starting from some point, and repeatedly walking counterclockwise around the triangle formed by the three e's. This length can be unbounded, so the output is "Infinity"