34952번 - 동전 뒤집기 게임과 쿼리

문제

정화와 은채는 동전 뒤집기 게임을 하고 있다. 초기에는 동전 $N$개가 일렬로 놓여 있고, 각 동전은 앞면 또는 뒷면이 위로 와 있다. 게임은 정화부터 시작해서 번갈아 가며 진행된다.

정화가 자신의 턴에 할 수 있는 행동은 다음과 같다.

• 앞면으로만 이루어진 최대 연속 구간 중 하나를 선택하여 그 구간의 동전을 모두 뒷면으로 뒤집고 은채에게 턴을 넘겨준다.
• 만약 앞면이 위로 와 있는 동전이 하나도 없다면, 행동을 하지 않고 은채에게 턴을 넘겨준다.

은채가 자신의 턴에 할 수 있는 행동은 다음과 같다.

• 뒷면으로만 이루어진 최대 연속 구간 중 하나를 선택하여 그 구간의 동전을 모두 앞면으로 뒤집고 정화에게 턴을 넘겨준다.
• 만약 뒷면이 위로 와 있는 동전이 하나도 없다면, 행동을 하지 않고 정화에게 턴을 넘겨준다.

모든 동전을 한 번에 뒤집는 사람이 승리한다.

여기서 최대 연속 구간이란, 구간 내 모든 동전의 면이 같고, 구간의 양 끝 바깥에는 동전이 없거나 반대 면의 동전이 있는 구간을 말한다. 다만, 선택 가능한 최대 연속 구간들 중 가장 긴 구간을 선택할 필요는 없다. 예를 들어, THHHTH에서 정화는 가운데 HHH 전체를 선택하거나 오른쪽 끝의 H를 선택할 수 있다.

둘이 게임을 하는 것을 지켜보던 지은이는 동전들의 상태 변화에 따라 누가 승리하는지에 대한 궁금증을 해결하기 위해 $Q$회에 걸쳐 다음 두 가지 행동 중 하나를 수행한다.

• 1ドル$ $i$: $i$번째의 동전을 뒤집는다. (1ドル ≤ i ≤ N$)
• 2ドル$ $l$ $r$: $l$번째부터 $r$번째까지의 동전들을 사용하여 게임을 진행했을 때 누가 승리하는지 구한다. (1ドル ≤ l ≤ r ≤ N$)

1ドル$번 행동으로 인한 동전들의 상태 변화는 누적되며, 다음 행동에 계속해서 반영된다. 2ドル$번 행동에 대해서는 해당 구간으로 게임을 진행한다고 가정했을 때의 승자를 구하는 것이고, 따라서 2ドル$번 행동은 동전들의 상태를 변화시키지 않는다.

두 사람 모두 최선의 전략으로 플레이한다고 가정할 때, 지은이가 2ドル$번 행동을 수행할 때마다 해당 구간에서 게임의 승자를 구하여라.

입력

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

둘째 줄에 초기 동전의 상태를 의미하는 길이 $N$의 문자열이 주어진다. 이때, 앞면은 H로, 뒷면은 T로 표현한다.

셋째 줄에 지은이가 수행한 행동의 수 $Q$가 주어진다. (1ドル \leq Q \leq 500,000円$)

다음 $Q$개의 줄에 걸쳐, 각 줄에는 지은이가 수행할 행동에 대한 정보가 지문과 같은 형식으로 주어진다. 2ドル$번 행동이 최소 한 번 이상 주어짐이 보장된다.

출력

지은이의 2ドル$번 행동에 대한 게임의 결과를 한 줄에 하나씩 출력한다.

정화가 이긴다면 First를, 은채가 이긴다면 Second를 출력한다.

제한

노트