33895번 - 돌아온 밤양갱

문제

종학이는 2024 아주대학교 프로그래밍 경시대회에 출제된 밤양갱 문제를 보고 감명을 받아 새로운 게임을 만들었다.

daldidalgo가 총 $K$번 반복된 후, daldidan으로 끝나는 문자열을 $K$-밤양갱 문자열이라고 정의한다. 예를 들어 3ドル$-밤양갱 문자열은 daldidalgodaldidalgodaldidalgodaldidan이다.

컴퓨터에 $N$-밤양갱 문자열을 총 $M$개 입력하고자 한다. $i$번 문자열은 현재 $A_i$개의 문자가 입력되어 있다. 현재 입력된 부분은 빈 문자열이거나, $N$-밤양갱 문자열의 접두사임이 보장된다.

종학이는 현재 상태에서 두 사람이 번갈아 가며 문자를 입력하여 더 이상 문자를 입력할 수 없는 사람이 지는 게임을 하려고 했지만, 이 말을 듣던 현빈이가 게임이 단조롭다며 자신이 제시하는 쿼리를 처리해 보라고 했다. 현빈이가 제시하는 쿼리는 다음과 같다.

• 1 L R T: $L$번부터 $R$번까지의 문자열과 고정된 길이 $T$의 문자열 $S$에 대해 게임을 시작할 때, 누가 이기는지 출력한다. 게임의 자세한 규칙은 다음과 같다. $(1 \le L \le R \le M;$ 0ドル \le T \le 10 \cdot N + 8)$
  • 종학이부터 시작하여 종학이와 현빈이가 번갈아 가며 문자를 입력한다.
  • 문자의 입력은 문자를 입력할 문자열의 번호 $P$를 선택한 후 다음의 세 가지 방법 중 한 가지 방법으로 진행한다. $(L \le P \le R)$
    1. 알파벳 소문자 a부터 z 중에서 자신이 원하는 알파벳을 하나 정해 $P$번 문자열의 맨 뒤에 입력한다.
    2. 지금까지 입력된 $P$번 문자열의 비어 있지 않은 연속된 부분 문자열을 복사하여 $P$번 문자열의 맨 뒤에 붙여 넣는다.
    3. 고정된 문자열 $S$의 비어 있지 않은 연속된 부분 문자열을 복사하여 $P$번 문자열의 맨 뒤에 붙여 넣는다.
  • 모든 $i$에 대해 항상 $i$번 문자열은 빈 문자열이거나, $N$-밤양갱 문자열의 접두사여야 한다.
  • 고정된 문자열 $S$는 게임 도중 변하지 않으며, $S$는 $N$-밤양갱 문자열의 접두사이다.
  • 더 이상 문자를 입력할 수 없게 된 사람이 진다.
• 2 X T: $X$번 문자열의 길이를 $T$로 변경한다. 변경한 문자열도 빈 문자열이거나, $N$-밤양갱 문자열의 접두사임이 보장된다. $(1 \le X \le M;$ 0ドル \le T \le 10 \cdot N + 8)$

종학이는 현빈이가 제시하는 쿼리가 너무 어려워서 답변을 내지 못하고 있다. 현빈이가 제시하는 쿼리를 처리하는 프로그램을 작성해서 종학이를 도와주자!

입력

첫 번째 줄에 입력할 밤양갱 문자열에서 daldidalgo가 반복되는 횟수 $N,ドル 전체 문자열의 개수 $M,ドル 현빈이가 제시하는 쿼리의 수 $Q$가 공백으로 구분되어 주어진다. $(0 \le N \le 200;$ 1ドル \le M, Q \le 3,000円)$

두 번째 줄에 $A_1, A_2, \cdots, A_M$이 공백으로 구분되어 주어진다. $A_i$는 현재 $i$번째 문자열에 입력되어 있는 문자의 수이다. $(0 \le A_i \le 10 \cdot N + 8)$

세 번째 줄부터 $Q$개의 줄에 걸쳐 현빈이가 제시하는 쿼리가 주어진다. 1ドル$번 쿼리가 한 개 이상 주어짐이 보장된다.

입력으로 주어지는 수는 모두 정수이다.

출력

1ドル$번 쿼리가 주어질 때 마다, 종학이가 이긴다면 First, 현빈이가 이긴다면 Second를 한 줄에 하나씩 출력한다.

제한

힌트