Home

Problem Statement

There is a string $s$ of length $3$ or greater. No two neighboring characters in $s$ are equal.

Takahashi and Aoki will play a game against each other. The two players alternately performs the following operation, Takahashi going first:

• Remove one of the characters in $s$, excluding both ends. However, a character cannot be removed if removal of the character would result in two neighboring equal characters in $s$.

The player who becomes unable to perform the operation, loses the game. Determine which player will win when the two play optimally.

Constraints

• $3 ≤ |s| ≤ 10^5$
• $s$ consists of lowercase English letters.
• No two neighboring characters in $s$ are equal.

Sample Input 1

aba

Sample Output 1

Second

Takahashi, who goes first, cannot perform the operation, since removal of the b, which is the only character not at either ends of $s$, would result in $s$ becoming aa, with two as neighboring.

Sample Input 2

abc

Sample Output 2

First

When Takahashi removes b from $s$, it becomes ac. Then, Aoki cannot perform the operation, since there is no character in $s$, excluding both ends.

Sample Input 3

abcab

Sample Output 3

First