34191번 - 돌 뒤집기 게임

문제

철수와 영희는 돌 뒤집기 게임을 하려고 한다.

돌 뒤집기 게임은 앞면과 뒷면을 구분할 수 있는 $N$개의 돌을 사용한다. 게임을 시작하기 전 심판은 $N$개의 돌을 일렬로 배치한다. 이때 1ドル \leq i < N$에 대해 $i$번째 돌과 $i+1$번째 돌은 서로 인접해 있다. 각 돌은 앞면 또는 뒷면이 보이도록 놓여 있으며, 초기에 최소 1ドル$개 이상의 돌은 앞면이 보이도록 배치되어 있다. 게임은 철수부터 시작해서 아래의 과정을 수행하며 턴을 진행한다.

1. 앞면이 보이는 돌 하나를 고른다. 만약 앞면이 보이는 돌이 없다면 패배한다.
2. 1ドル$번 과정에서 고른 돌을 뒤집어서 뒷면이 보이도록 바꾼다.
3. 뒤집은 돌의 인접한 돌 중 앞면이 보이는 돌이 2ドル$개라면 1ドル$번 과정으로 돌아간다. 그렇지 않다면 상대에게 차례를 넘긴다.

두 사람은 이 게임의 필승법을 알고 있으며, 이를 활용하여 자신의 턴을 진행한다. 게임을 시작하기 전 돌의 초기 상태가 입력으로 주어졌을 때 누가 승리하는지 판단해 보자.

입력

첫 줄에 돌의 개수 $N$이 주어진다. (1ドル \leq N \leq 1,000円,000円$)

둘째 줄에 길이 $N$의 문자열이 주어진다. $i$번째 문자는 $i$번째 돌의 초기 상태를 의미하며, H면 앞면, T면 뒷면이 보이고 있음을 의미한다.

출력

철수가 이긴다면 First, 영희가 이긴다면 Second를 출력한다.

제한

힌트