You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

小红帽正在和菜鸡学姐玩一个游戏，在他们面前有n个公道杯（在欧洲称为毕达哥拉斯杯）。用公道杯饮酒之时，只要不斟满，则与常杯无异。若斟满，则酒会从底孔完全流光。公道杯的结构如下图。

Description

在初始阶段，向 n 个空公道杯依次倒入酒，可能倒入如下三种分量的酒：不倒酒，用大写英文字母 E 表示；半杯酒，用大写英文字母 H 表示；一整杯酒，用大写英文字母 F 表示。

然后，每一次 小红帽 和 菜鸡学姐 可以选择一个 非空 的公道杯，将它之中的所有酒倒入它右边的公道杯中。若选择最右边的公道杯，则可以直接将其倒掉。

在公道杯的任意时刻，当酒满了的时候，会立刻流光变成空杯。若一个公道杯是半满的状态，向其中再倒半杯酒，则会因为满了而流空。

小红帽 和 菜鸡学姐 依次进行操作，小红帽 先进行第一次操作。当 小红帽 或 菜鸡学姐 在场上没有可以选取的公道杯时，则无法选取公道杯的人输掉了游戏。假设 小红帽 和 菜鸡学姐 都非常聪明，采取最优做法，问 小红帽 和 菜鸡学姐 谁获胜。

Format

Input

输入共一行一个字符串 S (1≤∣S∣≤10^6)。字符串的长度 ∣S∣ 就是公道杯的个数 n。

S_i 为大写英文字母 EHF 中的一个，表示第 i 个公道杯在最开始要倒多少酒。不倒酒，用大写英文字母 E 表示；半杯酒，用大写英文字母 H 表示；一整杯酒，用大写英文字母 F 表示。

Output

输出共一行一个字符串。

若 小红帽 获胜输出 shuai；若 菜鸡学姐 获胜输出 cai。

Samples

HEFH

shuai

HEHEFHEHFE

cai

Limitation

1s, 1024KiB for each test case.