G - SCSC Game Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

表示言語

/ /

Score : 100 points

Problem Statement

This year, FuriosaAI officially announced mass production of RNGD, its second-generation AI accelerator. RNGD is specialized for processing language models and multimodal models, and provides powerful computing performance even with low power consumption.

At SCSC, AI agents Lulu and Terra were created using RNGD chips, and SCSC had them play the SCSC game for performance testing.

The SCSC game is played with a string S consisting of uppercase letters S and C that does not contain SCSC as a substring. Lulu and Terra take turns, with Terra going first. On each turn, the current player chooses one character from the string and removes it. If, after the removal, the string contains SCSC as a substring, that player wins and the other player loses. If the current player can no longer choose any character to remove, that player loses and the other player wins.

Thanks to the powerful computing performance of the RNGD chips, Lulu and Terra have become able to always find optimal moves to win. Given the string S, determine which agent wins the game if both Lulu and Terra play optimally.

What is a substring? A substring of a string is a contiguous part of the original string. For example, `bc` is a substring of `abcd`, but `ac` is not. Multiple substrings may overlap within the same string. For example, `aba` appears a total of 2 times in `ababa`.

Constraints

  • 1 \leq T \leq 10\,000
  • 1 \leq |S| \leq 200\,000
  • S consists only of uppercase letters S and C, and does not contain SCSC as a substring.
  • The sum of |S| over all test cases does not exceed 200\,000.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

S

Output

For each test case, output Terra if Terra wins, and Lulu if Lulu wins, one per line.

Sample Input 1

2
SCSSCCS
SSSS

Sample Output 1

Terra
Lulu

表示言語

/ /

Score : 100 points

문제

FuriosaAI는 올해 공식적으로 2세대 AI 가속기 RNGD의 대량 생산을 발표했다. RNGD는 언어 모델 및 멀티모달 모델 처리에 특화된 제품으로, 적은 전력으로도 강력한 연산 성능을 제공한다.

SCSC에서는 RNGD 칩을 이용해 AI 에이전트 루루와 테라를 제작하고 성능 테스트를 위해 SCSC 게임을 플레이하도록 했다.

SCSC 게임은 알파벳 대문자 S와 C로 이루어진 문자열 중 SCSC를 부분문자열로 가지지 않는 문자열 S를 가지고 진행하는 게임이다. 루루와 테라는 테라부터 시작해 번갈아 가며 S의 문자 하나를 선택해 제거한다. 제거한 뒤 S가 SCSC를 부분문자열로 가지면 해당 에이전트가 승리하고 상대방이 패배한다. 만약 더 이상 문자를 선택해 제거할 수 없으면 해당 에이전트가 패배하고 상대방이 승리한다.

RNGD 칩의 강력한 연산 성능으로 루루와 테라는 항상 이기기 위한 최선의 행동을 찾아낼 수 있게 되었다. 문자열 S가 주어질 때 루루와 테라가 모두 최선의 행동을 하면 어느 에이전트가 게임에서 승리할지 구해 보자.

부분문자열이란 어떤 문자열의 부분문자열은 원래 문자열의 연속된 일부이다. 예를 들어 문자열 `abcd`에서 `bc`는 부분문자열이지만, `ac`는 부분문자열이 아니다. 같은 문자열 안에서 여러 부분문자열이 서로 겹쳐서 등장할 수도 있다. 예를 들어 문자열 `ababa`에서 `aba`는 총 2회 등장한다.

제한

  • 1 \leq T \leq 10\,000
  • 1 \leq |S| \leq 200\,000
  • S는 대문자 S와 C로만 이루어져 있으며, SCSC를 부분문자열로 가지지 않는다.
  • 모든 테스트 케이스의 |S|의 합은 200\,000을 넘지 않는다.

입력

입력은 다음 형식으로 표준 입력으로 주어진다.

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

각 테스트 케이스는 다음 형식으로 주어진다.

S

출력

각 테스트 케이스마다 테라가 이기면 Terra, 루루가 이기면 Lulu를 한 줄에 하나씩 출력한다.

입력 예 1

2
SCSSCCS
SSSS

출력 예 1

Terra
Lulu

表示言語

/ /

配点 : 100 点

問題文

FuriosaAI は今年，第 2 世代 AI アクセラレータである RNGD の大量生産を正式に発表した．RNGD は言語モデルおよびマルチモーダルモデルの処理に特化した製品であり，少ない電力でも強力な演算性能を提供する．

SCSC では RNGD チップを用いて AI エージェントのルルとテラを作成し，性能テストのために SCSC ゲームをプレイさせた．

SCSC ゲームは，英大文字 S と C からなる文字列のうち，SCSC を部分文字列として含まない文字列 S を用いて行うゲームである． ルルとテラはテラを先手として，交互に文字列の文字を 1 つ選んで削除する． 削除した後，文字列が SCSC を部分文字列として含むなら，そのプレイヤーが勝利し，相手が敗北する． もしこれ以上文字を選んで削除できなければ，そのプレイヤーが敗北し，相手が勝利する．

RNGD チップの強力な演算性能により，ルルとテラは常に勝つための最善の行動を見つけられるようになった． 文字列 S が与えられたとき，ルルとテラがともに最善の行動をとるなら，どちらのエージェントがゲームに勝利するか求めよ．

部分文字列とは ある文字列の 部分文字列 とは，元の文字列の連続した一部分である．例えば，文字列 `abcd` において `bc` は部分文字列であるが，`ac` は部分文字列ではない． 同じ文字列の中で，複数の部分文字列が互いに重なって現れることもある．例えば，文字列 `ababa` において `aba` は合計 2 回現れる．

制約

  • 1 \leq T \leq 10\,000
  • 1 \leq |S| \leq 200\,000
  • S は英大文字 S と C のみからなり，SCSC を部分文字列として含まない．
  • すべてのテストケースにおける |S| の総和は 200\,000 を超えない．

入力

入力は以下の形式で標準入力から与えられる．

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各テストケースは次の形式で与えられる．

S

出力

各テストケースについて，テラが勝つなら Terra，ルルが勝つなら Lulu を 1 行に出力せよ．

入力例 1

2
SCSSCCS
SSSS

出力例 1

Terra
Lulu