No.154 市バス

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 64 MB / 通常問題
タグ : / 解いたユーザー数 202
作問者 : LayCurseLayCurse
14 ProblemId : 372 / 出題時の順位表

問題文

京都の市バスは,いくつかの系統のバスが走っています.
各系統ごとに,その日の最終バスと最終バスの $1$ つ前のバスは,表示板のライトの色が通常と違います.
通常のライトの色は白ですが,最終バスの1つ前のバスのライトの色は緑,最終バスのライトの色は赤になります.
yukiさんは始発から終バスまで,とある道路で通る全てのバスのライトの色をチェックして,ライトの色を見た順番にメモに残しました.
yukiさんはメモを間違えて取ってないかを心配です.
このメモが示すライトの色の順番があり得るパターンなのかどうかをチェックするプログラムを書いてください.
ただし,全ての系統の市バスは毎日 $3$ 本以上走っており,$1$ 日を通じて同じ経路を通るとする.


図1.京都の市バス3系統だが,これは通常のライトである.ちなみに,緑や赤のライトだと若干文字が読みにくくなる(百万遍にて,2015年2月4日)

入力

インプットの $1$ 行目には,テストケースの数を表す整数 $T$ が書かれている.
各テストケースは $1$ 行からなり,文字列 $S$ が与えられる.
文字列 $S$ の $i$ 文字目は,その日のyukiさんのメモで $i$ 番目に見たバスのライトの色が示されており,$\verb|W|$ は白,$\verb|G|$ は緑,$\verb|R|$ は赤を意味する.その他の文字は含まれない.

  • $1 \leq T \leq 1000$
  • $1 \leq |S| \leq 1000$

出力

各テストケースに対して,あり得るパターンなら $\verb|possible|$ を,そうでないなら $\verb|impossible|$ を出力して下さい.

サンプル

サンプル1
入力
5
WWWWWWWWWGR
WWWWGWGRR
WWWWWWWWWWWWWWGRRG
WGRWGR
WWWWWWWWWWWWWWWWWGGWGWGGWGWGGGWGG
出力
possible
possible
impossible
possible
impossible

1つ目のテストケース:1つの系統のバスしかありません.
2つ目のテストケース:2つの系統のバスがあります.
3つ目のテストケース:片方の系統において,終バスの後に緑のライトのバスが走っている感じでなんかおかしいです.
4つ目のテストケース:1つの系統の終バスが終わってから,もう一方の系統が走り始めるなんてこともあるんですね.
5つ目のテストケース:終バスがないなんてことはない.

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。