Problem: Unknown pathogen

Dr. Hideyo discovered an unknown pathogen. This pathogen has a chain structure in which two types of bacteria called Akdamakin and Zendamakin are linked in a straight line. We want to detoxify this pathogen for humankind.

It is known that this pathogen weakens when the length is 2 or less and is detoxified by immunity. Dr. Hideyo can cut this pathogen anywhere to make two chains, the first half and the second half. You can also connect two chains into one chain.

However, it should be noted that chains with a large number of Akdamakin are extremely harmful. When the number of Akdamakins in a chain exceeds the number of Zendamakins, the Akdamakins begin to grow indefinitely at that moment. This is no exception for chains with a length of 2 or less, so you must carefully cut the chains.

Is it possible to make one chain harmless by making it 2 or less in length without making a chain that has more Akdamakins at any moment? Dr. Hideyo has instructed you, your assistant, to write a program to determine if detoxification is possible. Create a program that outputs the operation if detoxification is possible, and outputs that it is impossible if it is not possible. However, the number of steps for that operation does not have to be minimal.

Input / output example

Input example


6
oooxxxx
ooooxxx
oxxooxxo
ooxx
oo
ooo


Output example


-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


For example, the second pathogen ooooxxx in the input example
split 0 0 creates o (1) and oooxxx (2). Here, the numbers in parentheses represent identification numbers.
join 2 1 creates oooxxxo (3) and 1 and 2 disappear.
split 3 4 gives oooxx (4) and xo (5). At this time, there is a chain of {oooxx (4), xo (5)}.
split 40 produces o (6) and ooxx (7). {xo (5), o (6), ooxx (7)}
ooxxo (8) can be created by join 7 6. {xo (5), ooxxo (8)}
split 8 2 produces oox (9) and xo (10). {xo (5), oox (9), xo (10)}
The split 90 results in {xo (5), xo (10), o (11), ox (12)} and ends.



input

The input is given in the following format.


Q
str1
str2
::
strQ


The number of pathogens Q (1 ≤ Q ≤ 300) is given on the first line. The following Q line is given a single string stri consisting of'o'(Zendamakin) and'x' (Akudamakin) representing the initial state of each pathogen. The length of the string stri is 1 or more and 100 or less.

output

For stri, if there is a column of disconnect / join operations that meets the requirements, the first row of output outputs an integer n representing the length of the operation column, and the following n rows contain the operation content 1 per row. Outputs each operation in order from the first operation.

The disconnect operation should be expressed in the following format.


split a p


a is an integer representing the identification number of the chain to be cut, and p is the position to cut the chain. As a result of this operation, chain a is cleaved immediately after the p-th (serial number starting with 0) fungus from the beginning. Of the two new chains, the first half is given the identification number m + 1 and the second half is given the identification number m + 2 (where m represents the highest identification number ever assigned. ). Also, the chain a disappears.

The join operation should be expressed in the following format.


join a b


a and b are integers representing the identification numbers of the chains to be joined. The result of this operation is a new chain with the beginning of chain b joined to the end of chain a. The newly created strand is given the identification number m + 1 (where m represents the highest identification number ever given). Also, the chains a and b disappear.

The first strand given as input is given the identification number 0.

As a result of the operation, if the chain is disassembled to meet the requirements of the problem, any operation is judged to be the correct answer. The length of the operation sequence does not necessarily have to be the shortest. However, the length of the operation sequence must be 20000 or less. Whenever a chain is decomposable in a dataset, it is guaranteed that there is an operating sequence that meets this condition.

If an invalid operation sequence is output, it is judged as an incorrect answer. The illegal operation sequence includes the following cases.

* If 0 ≤ p <(length of chain a) -1 is not satisfied in the split operation split a p.
* When the identification number of the chain to be the target of the cutting / joining operation has not been generated yet, or when it has disappeared because it has already been the target of another operation.
* In the join operation join a b, if a and b are equal.



If there is no disconnect / join operation column that satisfies the request, "-1" is output.

Example

Input

6
oooxxxx
ooooxxx
oxxooxxo
ooxx
oo
ooo


Output

-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

Solution (in CPP):

Solution:
#include "bits/stdc++.h"
using namespace std;

struct chane {
	int id;
	string st;
};
struct ope {
	bool split;
	int a;
	int b;
};
int check_cut(chane&c) {
	int xnum = (count(c.st.begin(), c.st.end(), 'x'));
	int onum = (count(c.st.begin(), c.st.end(), 'o'));
	if (xnum == onum)return -1;
	else {
		assert(xnum < onum);
		int nowx = 0;
		int nowo = 0;
		for (int i = 0; i < c.st.size()-1; ++i) {
			if (c.st[i] == 'o')nowo++;
			else nowx++;
			if (nowo == nowx + (onum - xnum) - 1) {
				assert(c.st[0] == 'o' || c.st[i] == 'o');
				return i;
			}
			if (nowx + 1 == nowo) {
				assert(c.st[c.st.size() - 1] == 'o' || c.st[i + 1] == 'o');
				return i;
			}
		}
	}
	return -1;
}
int make_ox(chane&c) {
	if (c.st[0]!=c.st[1]) {
		return 1;
	}
	if (c.st[c.st.size() - 2]!=c.st[c.st.size() - 1]) {
		return c.st.size() - 3;
	}
	return -1;
}
int needo(chane&c) {
	int xnum = (count(c.st.begin(), c.st.end(), 'x'));
	int onum = (count(c.st.begin(), c.st.end(), 'o'));
	if (xnum != onum) {
		return -1;
	}
	else {
		if (c.st[0] == 'x')return 0;
		if (c.st[c.st.size() - 1])return 1;
		return -1;
	}
}


void cut_chane(vector<ope>&opes,const int place, const chane& ch,vector<chane>&newcs,int& nextid) {
	opes.push_back(ope{ true,ch.id,place });
	newcs.push_back(chane{ nextid++,ch.st.substr(0,place + 1) });
	newcs.push_back(chane{ nextid++,ch.st.substr(place + 1,ch.st.size() - place - 1) });
}
void solve(const string& ast) {
	vector <ope>opes;
	chane base(chane{ 0, ast });
	const int xnum = count(ast.begin(), ast.end(), 'x');
	if (ast.size() < 2 *xnum ) {
		cout << -1 << endl;
		return;
	}
	else if (ast.size() == 2 * xnum) {
		int num =0;
		while (base.st.size()>2) {
			if (make_ox(base) == 1) {
				opes.push_back(ope{ true,num,1 });
				num += 2;
				base.st = base.st.substr(2, base.st.size() - 2);
			}
			else {
				cout << -1 << endl;
				return;
			}
		}
	}
	else {
		vector<chane>cs;
		cs.push_back(chane{ 0,ast });
		int nextid = 1;
		while (any_of(cs.begin(), cs.end(), [](const chane&c) { return c.st.size() >= 3; })) {
			bool flag = true;
			while ( flag) {
				flag = false;
				{
					vector<chane>newcs;
					for (int i = 0; i < cs.size(); ++i) {
						if (cs[i].st.size() >= 3) {
							const int cut = make_ox(cs[i]);
							if (cut != -1) {
								flag = true;
								cut_chane(opes, cut, cs[i], newcs, nextid);
								//opes.push_back(ope{ true,cs[i].id,cut });
								//newcs.push_back(chane{ nextid++,cs[i].st.substr(0,cut + 1) });
								//newcs.push_back(chane{ nextid++,cs[i].st.substr(cut + 1,cs[i].st.size() - cut - 1) });
							}
							else {
								newcs.push_back(cs[i]);
							}
						}
						else if (cs[i].st.size() == 1) {
							newcs.push_back(cs[i]);
						}
					}
					cs = newcs;
				}
				if (!any_of(cs.begin(), cs.end(), [](const chane&c) { return c.st.size() >= 3; }))break;
				{
					vector<chane>newcs;
					for (int i = 0; i < cs.size(); ++i) {
						if (cs[i].st.size() != 2) {
							newcs.push_back(cs[i]);
						}
					}
					cs = newcs;
				}
			}
			if (!any_of(cs.begin(), cs.end(), [](const chane&c) { return c.st.size() >= 3; }))break;
			{
				vector<chane>newcs;
				for (int i = 0; i < cs.size(); ++i) {
					const int cut = check_cut(cs[i]);
					if (cut != -1) {
						opes.push_back(ope{ true,cs[i].id,cut });
						newcs.push_back(chane{ nextid++,cs[i].st.substr(0,cut + 1) });
						newcs.push_back(chane{ nextid++,cs[i].st.substr(cut + 1,cs[i].st.size() - cut - 1) });
					}
					else {
						newcs.push_back(cs[i]);
					}
				}
				cs = newcs;
			}
			if (!any_of(cs.begin(), cs.end(), [](const chane&c) { return c.st.size() >= 3; }))break;
			{
				int aid = -1;
				for (int i = 0; i < cs.size(); ++i) {
					if (cs[i].st.size() == 1) {
						assert(cs[i].st[0] == 'o');
						aid = cs[i].id;
						break;
					}
				}
				if (aid != -1) {
					vector<chane>newcs;
					bool used = false;
					for (int i = 0; i < cs.size(); ++i) {
						if (cs[i].id == aid)continue;
						int aneed = needo(cs[i]);
						if (aneed == -1||used) {
							newcs.push_back(cs[i]);
						}
						else if (aneed == 0) {
							used = true;
							opes.push_back(ope{ false,aid,cs[i].id });
							newcs.push_back(chane{ nextid++,'o' + cs[i].st });
						}
						else {
							used = true;
							opes.push_back(ope{ false,cs[i].id,aid });
							newcs.push_back(chane{ nextid++, cs[i].st + 'o' });
						}
					}
					if (!used) {
						newcs.push_back(chane{ aid,"o" });
					}
					cs = newcs;
				}
			}
		}
	}
	cout << opes.size() << endl;
	for (auto op : opes) {
		if (op.split)cout << "split ";
		else cout << "join ";
		cout << op.a << " " << op.b << endl;
	}
}

int main() {
	int Q; cin >> Q;
	while (Q--) {
		string st; cin >> st;
		solve(st);
	}
	return 0;
}