配点 : $300$ 点

問題文

文字列 $X$ が与えられます。$X$ の長さは偶数であり、半分は S 、もう半分は T からなります。

高橋君は ST という文字列が苦手です。なので以下の操作を $10^{10000}$ 回行うことにしました。

• $X$ の(連続な)部分文字列で ST となるもののうち、最も左側にあるものを取り除く。存在しないならば何もしない。

最終的に $X$ は何文字になるかを求めてください。

制約

• $2 \leq |X| \leq 200,000$
• $X$ の長さは偶数
• $X$ を構成する文字のうち半分は S であり、もう半分は T である

部分点

• $200$ 点分のデータセットでは $|X| \leq 200$ が成り立つ

入力

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

$X$

出力

$1$ 行に問題の答えを出力する。

TSTTSS

4

$1$ 回目の操作では TSTTSS の $2,3$ 文字目が ST なので取り除きます。 $X$ は TTSS になり、もう ST はないため残り $10^{10000}-1$ 回は何もしません。 よって答えは $4$ となります。

SSTTST

0

SSTTST ⇒ STST ⇒ ST ⇒ `` となり、最終的に空文字列になります。

TSSTTTSS

4

TSSTTTSS ⇒ TSTTSS ⇒ TTSS となります。