301614: CF305E. Playing with String

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Playing with String

题意翻译

给出一个字符串 $s$,两人轮流操作,每次选出一个位置i满足 $s_{i-1}=s_{i+1}$ ,那么之后s会分成三个串 $s_{1,i-1},s_{i,i},s_{i+1,n}$ 。谁先不能操作谁输。先手能赢的话输出先手第一次可以操作的最小位置?

题目描述

Two 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. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF305E/e3dc20c8c09e1180ec4786b230762f8e7c79cfda.png)An example of the initial situation at $ s $ = "abacaba"A player's move is the sequence of actions: 1. 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. 2. 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&lt;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} $ . 3. 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|} $ . ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF305E/4da2b2c4651d8ec70c1d3e569c51588926a9324c.png)An example of making action $ (i=4) $ with string $ s $ = «abacaba»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.

输入输出格式

输入格式


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

输出格式


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|) $ .

输入输出样例

输入样例 #1

abacaba

输出样例 #1

First
2

输入样例 #2

abcde

输出样例 #2

Second

说明

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.

Input

题意翻译

给出一个字符串 $s$,两人轮流操作,每次选出一个位置i满足 $s_{i-1}=s_{i+1}$ ,那么之后s会分成三个串 $s_{1,i-1},s_{i,i},s_{i+1,n}$ 。谁先不能操作谁输。先手能赢的话输出先手第一次可以操作的最小位置?

加入题单

上一题 下一题 算法标签: