#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; ifstream fin("zero.txt"); #define cin fin long long hash(const vector& field) { long long l = 0; for (int i = 0; i < 10; ++i) { l = l * 16 + field[i]; } return l; } inline int get_nth(long long f, int n) { f >>= (9 - n) * 4; return (f & 15); } inline void set_nth(long long& f, int n, long long k) { k <<= (9 - n) * 4; f = k | (f & ~(15LL << (9-n)*4)); } struct history_t { history_t* next; int t; history_t(int t, history_t* next) : t(t), next(next) {} }; struct hand { history_t* history; // 10 >= -> R long long field; hand() : history(0), field(0) {} }; void solve(const vector& field_orig) { if (accumulate(field_orig.begin(), field_orig.end(), 0) % 10 != 0) { cout << "Impossible" << endl; return; } set visited; queue hands; visited.insert(hash(field_orig)); hand h; h.history = NULL; h.field = hash(field_orig); hands.push(h); while (!hands.empty()) { hand h = hands.front(); hands.pop(); for (int i = 0; i < 10; ++i) { if (get_nth(h.field, i) == 0) { continue; } // left if (i != 0) { int left = abs(i - get_nth(h.field, i)); hand h2; h2.field = h.field; if (i != left) { set_nth(h2.field, i, 0); set_nth(h2.field, left, (get_nth(h.field, i) + get_nth(h.field, left)) % 10); } long long hashed = h2.field; if (!visited.count(hashed)) { history_t* hist = new history_t(i, h.history); h2.history = hist; hands.push(h2); visited.insert(hashed); if (hashed == 0) { list history; for (history_t* p = h2.history; p != NULL; p = p->next) { history.push_front(p->t); } for (list::iterator it = history.begin(); it != history.end(); ++it) { if (*it >= 10) { cout << 'R'; } else { cout << 'L'; } *it %= 10; cout << char(*it + 'a') << endl; } return; } } } // right if (i != 9) { int right = i + get_nth(h.field, i); if (right > 9) { right = 9 - (right - 9); } hand h2; h2.field = h.field; if (i != right) { set_nth(h2.field, i, 0); set_nth(h2.field, right, (get_nth(h.field, i) + get_nth(h.field, right)) % 10); } long long hashed = h2.field; if (!visited.count(hashed)) { history_t* hist = new history_t(i + 10, h.history); h2.history = hist; hands.push(h2); visited.insert(hashed); if (hashed == 0) { list history; for (history_t* p = h2.history; p != NULL; p = p->next) { history.push_front(p->t); } for (list::iterator it = history.begin(); it != history.end(); ++it) { if (*it >= 10) { cout << 'R'; } else { cout << 'L'; } *it %= 10; cout << char(*it + 'a') << endl; } return; } } } } } cout << "Impossible" << endl; } int main() { if(!fin) return -1; int N; cin >> N; while (N--) { vector field(10); for (int i = 0; i < 10; ++i) { char c; cin >> c; if (c == '-') { field[i] = 0; } else { field[i] = c - '0'; } } solve(field); if (N) { cout << endl; } } return 0; }