Two players, Petya and Vanya, play the following game. There is a string
s that is 3 or more characters long. No two adjacent characters in
s are equal. The players take turns. Peter goes first. In one move, you need to remove one of the characters from the string
s, except for the extreme ones (the first and last). A symbol cannot be removed if the removal of the symbol would result in two adjacent identical symbols appearing in the line. A player who cannot complete the operation loses the game. Determine which player will win if they play optimally.
Input
The input is
s (
\(3 <= len(s) <= 10^5\)). The string consists only of lowercase English letters (
a-z). No two adjacent characters in
s are equal.
Imprint
If Petya wins, print
First. If Vanya wins, print
Second.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
aba
|
Second
|
Peter cannot perform the operation because deleting b, which is the only character that can be deleted, will cause s to become aa, two identical characters will be adjacent. |
| 2 |
abc
|
First
|
When Petya removes b from s, the string becomes ac and Vanya will not be able to perform the operation, because in s has no other characters except the outermost ones. |
| 3 |
abcab
|
First
|
|