英世博士は未知の病原菌を発見しました。この病原菌は、アクダマキンとゼンダマキンと呼ばれる二種類の菌が、一直線に連なった鎖状の構造をしています。人類のために、この病原菌を無害化したいと考えています。
この病原菌は、長さが２以下になると力が弱まり、免疫力によって無害化されることが分かっています。英世博士は、この病原菌を任意の場所で切断して、前半と後半の２つの鎖にすることができます。また、２つの鎖を連結して１つの鎖にすることもできます。
しかし注意しなければいけないのは、アクダマキンの数が多い鎖はきわめて有害だということです。ある鎖においてアクダマキンの数がゼンダマキンの数よりも多くなると、その瞬間アクダマキンは無制限に増殖を始めます。これは長さ２以下の鎖についても例外ではないので、慎重に鎖を切断していかなければなりません。
どの瞬間においてもアクダマキンの数の方が多いような鎖を作ることなく、一本の鎖を長さ２以下にして無害化することは可能でしょうか。英世博士は、助手であるあなたに無害化が可能かどうか判定するプログラムを作成するよう指示しました。無害化が可能ならばその操作を出力し、不可能ならば不可能であると出力するプログラムを作成してください。ただし、その操作のステップ数が最小である必要はありません。
入力は以下の形式で与えられる。
Q str1 str2 : strQ
1 行目に病原菌の数 Q (1 ≤ Q ≤ 300) が与えられる。続く Q 行に各病原菌の初期状態を表す 'o' (ゼンダマキン) および 'x' (アクダマキン) からなる１つの文字列 stri が与えられる。文字列 stri の長さは 1 以上 100 以下である。
stri について、要求を満たす切断・結合操作の列が存在する場合、出力の最初の行にはその操作列の長さを表す整数 n を出力し、続く n 行に操作の内容を１行に１操作ずつ、最初の操作から順に出力する。
切断操作は以下の形式で表すこと。
split a p
a は切断する鎖の識別番号を表す整数であり、p はその鎖を切断する位置である。この操作の結果、鎖 a は先頭から p 番目（先頭を 0 から始める通し番号)の菌の直後で切断される。新しくできる２つの鎖のうち、前半のものに識別番号 m+1 が、後半のものに識別番号 m+2 が付与される（ここで、m はこれまでに付与された最も大きな識別番号を表す）。また、鎖 a は消滅する。
結合操作は以下の形式で表すこと。
join a b
a, b は結合する鎖の識別番号を表す整数である。この操作の結果、鎖 a の末尾に鎖 b の先頭を結合した新しい鎖が作られる。新しく作られた鎖には、識別番号 m+1 が付与される(ここで、m はこれまでに付与された最も大きな識別番号を表す)。また、鎖 a, b は消滅する。
入力として与えられる最初の鎖には、識別番号 0 が付与されている。
操作の結果、問題の要求を満たすように鎖が分解されていた場合、どのような操作でも正答と判定される。操作列の長さも必ずしも最短である必要はない。ただし、操作列の長さは 20000 以下でなければならない。データセットにおいて、鎖が分解可能な場合、必ずこの条件を満たす操作列が存在することが保証される。
不正な操作列が出力された場合、誤答と判定される。不正な操作列には、以下の場合が含まれる。
要求を満たす切断・結合操作の列が存在しない場合、"-1"と出力する。
6 oooxxxx ooooxxx oxxooxxo ooxx oo ooo
-1 7 split 0 0 join 2 1 split 3 4 split 4 0 join 7 6 split 8 2 split 9 0 3 split 0 1 split 2 1 split 4 1 -1 0 1 split 0 0
例えば、入力例の２番目の病原菌 ooooxxx は、
split 0 0 により o(1) と oooxxx(2) ができる。ここで、()内の数字は識別番号を表す。
join 2 1 により oooxxxo(3) ができ 1 と 2 は消滅する。
split 3 4 により oooxx(4) と xo(5) ができる。このとき{ oooxx(4), xo(5) }の鎖が存在する。
split 4 0 により o(6) と ooxx(7) ができる。{ xo(5), o(6), ooxx(7)}
join 7 6 により ooxxo(8) ができる。{ xo(5), ooxxo(8)}
split 8 2 により oox(9) と xo(10) ができる。{xo(5), oox(9), xo(10) }
split 9 0 により { xo(5), xo(10), o(11), ox(12) } となって終了する。