A Die Maker

時間制限 : 8 sec, メモリ制限 : 65536 KB
英語版はこちら

サイコロ職人

サイコロ職人の朝は早い.

サイコロ職人であるあなたは,顧客からの注文を受け,日々様々なサイコロを製作している. 今日,あなたは正六面体の形状をしたサイコロで,6つの面のどこにでもよいから t1, t2, ..., t6 という数が印されたものを作って欲しい,という注文を受けた.

注文のサイコロを作るために,あなたは平らな板の形状をした専用工具を使う. あなたは最初,各面に 0 が書かれたサイコロを持っている. 工具の上でサイコロを東西南北のいずれかの方向に 90 度回転させると, 新しく下に来た面に書かれた数が 1 増加する. あなたは適切にサイコロを回転させることで,注文通りのサイコロを作ろうとしている.

最終的に面に書かれた数字は, 一連のステップでサイコロをどの方向に回転させるのかによって決まる. 各ステップでどの方向にサイコロを回転させたのかを表す文字列を操作列と呼ぶことにする. 正確には,次のように定義する. n 回サイコロを回転させる操作列は n 文字からなる. i ステップ目でサイコロを東方向に回転させた場合,操作列の i 文字目は E であるとする. 同様に, 西方向に回転させた場合は W, 南方向に回転させた場合は S, 北方向に回転させた場合は N であるとする. たとえば,NWS という操作列は,最初に北方向にサイコロを回転させ,次に西方向に回転させ,最後に南方向に回転させる,という3回転の操作を表す.

注文を表す 6 つの整数が与えられるので,注文どおりのサイコロを作る操作列を求めて欲しい. 複数の操作列がありうるので,辞書順で最も前である操作列を求めてほしい.

Input

入力は複数のデータセットからなる. データセットの個数は 40 個を超えない. 各データセットは次の形式で表される.

t1 t2 t3 t4 t5 t6
p q

t1, t2, ..., t6 は注文を表す整数である. また,pq は正の整数であり,出力する操作列の範囲を表す (詳しくは下記を参照せよ).

各データセットは 0 ≤ t1t2 ≤ ... ≤ t6 ≤ 5,000 および 1 ≤ pqt1+t2+...+t6 を満たす. 入力は 6 つのゼロからなる行で終わる.

Output

各データセットについて,注文されたサイコロを作る辞書順で最小の操作列の p 文字目から q 文字目までを出力せよ (p 文字目と q 文字目も含む). 作ることができない場合,impossible と出力せよ.

ここで辞書順は次のように再帰的に定義される. 空文字列は辞書順で最初に現れる. 2つの空でない文字列 x = x1 ... xky = y1 ... yl について,文字列 x が文字列 y より辞書順で前であるとは,

  • x1y1 よりアルファベット順 ('A'から'Z') で前である,または
  • x1y1 が同じ文字であり x2 ... xky2 ... yl よりも辞書順で前である

ことをいう.

Sample Input

1 1 1 1 1 1
1 6
1 1 1 1 1 1
4 5
0 0 0 0 0 2
1 2
0 0 2 2 2 4
5 9
1 2 3 4 5 6
15 16
0 1 2 3 5 9
13 16
2 13 22 27 31 91
100 170
0 0 0 0 0 0

Output for the Sample Input

EEENEE
NE
impossible
NSSNW
EN
EWNS
SNSNSNSNSNSNSNSNSNSNSNSSNSNSNSNSNSNSNSNSNSNSNSNSNSNSNSNSNSNSNSNSNSNWEWE

Source: ACM International Collegiate Programming Contest , Japan Domestic Contest, Tokyo, Japan, 2014-07-11
http://icpc.iisf.or.jp/2014-waseda/