Rating changes for last rounds are temporarily rolled back. They will be returned soon.
×

The package for this problem was not updated by the problem writer or Codeforces administration after we've upgraded the judging servers. To adjust the time limit constraint, a solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then the value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Playing with String

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputTwo people play the following string game. Initially the players have got some string *s*. The players move in turns, the player who cannot make a move loses.

Before the game began, the string is written on a piece of paper, one letter per cell.

A player's move is the sequence of actions:

- The player chooses one of the available pieces of paper with some string written on it. Let's denote it is
*t*. Note that initially, only one piece of paper is available. - The player chooses in the string
*t*=*t*_{1}*t*_{2}...*t*_{|t|}character in position*i*(1 ≤*i*≤ |*t*|) such that for some positive integer*l*(0 <*i*-*l*;*i*+*l*≤ |*t*|) the following equations hold:*t*_{i - 1}=*t*_{i + 1},*t*_{i - 2}=*t*_{i + 2}, ...,*t*_{i - l}=*t*_{i + l}. - Player cuts the cell with the chosen character. As a result of the operation, he gets three new pieces of paper, the first one will contain string
*t*_{1}*t*_{2}...*t*_{i - 1}, the second one will contain a string consisting of a single character*t*_{i}, the third one contains string*t*_{i + 1}*t*_{i + 2}...*t*_{|t|}.

Your task is to determine the winner provided that both players play optimally well. If the first player wins, find the position of character that is optimal to cut in his first move. If there are multiple positions, print the minimal possible one.

Input

The first line contains string *s* (1 ≤ |*s*| ≤ 5000). It is guaranteed that string *s* only contains lowercase English letters.

Output

If the second player wins, print in the single line "Second" (without the quotes). Otherwise, print in the first line "First" (without the quotes), and in the second line print the minimal possible winning move — integer *i* (1 ≤ *i* ≤ |*s*|).

Examples

Input

abacaba

Output

First

2

Input

abcde

Output

Second

Note

In the first sample the first player has multiple winning moves. But the minimum one is to cut the character in position 2.

In the second sample the first player has no available moves.

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/25/2022 14:58:02 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|