An Ordinary Game

AtCoder

IDarc064_b

Time2000ms

Memory256MB

Difficulty—

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. ## Input The input is given from Standard Input in the following format: $s$ [samples]

Samples

Input #1

aba

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 `a`s neighboring.

Input #2

abc

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.

Input #3

abcab

Output #3

First

API Response (JSON)

{
  "problem": {
    "name": "An Ordinary Game",
    "description": {
      "content": "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 followi",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc064_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There is a string $s$ of length $3$ or greater. No two neighboring characters in $s$ are equal.\nTakahashi and Aoki will play a game against each other. The two players alternately performs the followi...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments