Problem: Your friend Kirchhoff is shocked with the current state of electronics design.

"Ohmygosh! Watt is wrong with the field? All these circuits are inefficient! There's so much capacity for improvement. The electrical engineers must not conduct their classes very well. It's absolutely revolting" he said.

The negativity just keeps flowing out of him, but even after complaining so many times he still hasn't lepton the chance to directly change anything.

"These circuits have too much total resistance. Wire they designed this way? It's just causing a massive loss of resistors! Their entire field could conserve so much money if they just maximized the potential of their designs. Why can't they just try alternative ideas?"

The frequency of his protests about the electrical engineering department hertz your soul, so you have decided to take charge and help them yourself. You plan to create a program that will optimize the circuits while keeping the same circuit layout and maintaining the same effective resistance.

A circuit has two endpoints, and is associated with a certain constant, R, called its effective resistance. 

The circuits we'll consider will be formed from individual resistors joined together in series or in parallel, forming more complex circuits. The following image illustrates combining circuits in series or parallel. 

<image>

According to your friend Kirchhoff, the effective resistance can be calculated quite easily when joining circuits this way:

  * When joining k circuits in series with effective resistances R_1, R_2, …, R_k, the effective resistance R of the resulting circuit is the sum $$$R = R_1 + R_2 + … + R_k.$$$

  * When joining k circuits in parallel with effective resistances R_1, R_2, …, R_k, the effective resistance R of the resulting circuit is found by solving for R in $$$1/R = (1)/(R_1) + (1)/(R_2) + … + (1)/(R_k), assuming all R_i > 0; if at least one R_i = 0, then the effective resistance of the whole circuit is simply R = 0$$$. 



Circuits will be represented by strings. Individual resistors are represented by an asterisk, "*". For more complex circuits, suppose s_1, s_2, …, s_k represent k ≥ 2 circuits. Then:

  * "(s_1 S s_2 S … S s_k)" represents their series circuit; 
  * "(s_1 P s_2 P … P s_k)" represents their parallel circuit. 



For example, "(* P (* S *) P *)" represents the following circuit:

<image>

Given a circuit, your task is to assign the resistances of the individual resistors such that they satisfy the following requirements:

  * Each individual resistor has a nonnegative integer resistance value; 
  * The effective resistance of the whole circuit is r; 
  * The sum of the resistances of the individual resistors is minimized. 



If there are n individual resistors, then you need to output the list r_1, r_2, …, r_n (0 ≤ r_i, and r_i is an integer), where r_i is the resistance assigned to the i-th individual resistor that appears in the input (from left to right). If it is impossible to accomplish the task, you must say so as well.

If it is possible, then it is guaranteed that the minimum sum of resistances is at most 10^{18}. 

Input

The first line of input contains a single integer t (1 ≤ t ≤ 32000), denoting the number of test cases. The next lines contain descriptions of the test cases.

Each test case consists of a single line containing the integer r (1 ≤ r ≤ 10^6), space, and then the string representing the circuit. It is guaranteed that the string is valid and follows the description above. The number of individual resistors (symbols "*") is at least 1 and at most 80000.

It is guaranteed that the total number of individual resistors across all test cases is at most 320000.

Output

For each test case, print a single line:

  * If it's possible to achieve an effective resistance of r, print "REVOLTING" (without quotes) and then n integers r_1, r_2, …, r_n — the resistances assigned to the individual resistors. Here, n denotes the number of the individual resistors in the circuit. 

There may be multiple possible such assignments with a minimal sum of resistances of the individual resistors, you can output any of them;

  * If it's impossible, print the string: "LOSS" (without quotes). 

Example

Input


3
5 *
1 (* S *)
1 (* P (* S *))


Output


REVOLTING 5
REVOLTING 1 0
REVOLTING 2 1 1

Note

The following illustrates the third sample case:

<image>

Here, the sum of the resistances of the individual resistors is 2 + 1 + 1 = 4, which can be shown to be the minimum. Note that there may be other assignments that achieve this minimum.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vd = vector<double>;
using vs = vector<string>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
using vpii = vector<pii>;
using vvpii = vector<vpii>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
using vpdd = vector<pdd>;
using vvpdd = vector<vpdd>;
template <typename T>
void ckmin(T& a, const T& b) {
  a = min(a, b);
}
template <typename T>
void ckmax(T& a, const T& b) {
  a = max(a, b);
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
namespace __input {
template <class T1, class T2>
void re(pair<T1, T2>& p);
template <class T>
void re(vector<T>& a);
template <class T, size_t SZ>
void re(array<T, SZ>& a);
template <class T>
void re(T& x) {
  cin >> x;
}
void re(double& x) {
  string t;
  re(t);
  x = stod(t);
}
template <class Arg, class... Args>
void re(Arg& first, Args&... rest) {
  re(first);
  re(rest...);
}
template <class T1, class T2>
void re(pair<T1, T2>& p) {
  re(p.first, p.second);
}
template <class T>
void re(vector<T>& a) {
  for (int i = 0; i < (int((a).size())); i++) re(a[i]);
}
template <class T, size_t SZ>
void re(array<T, SZ>& a) {
  for (int i = 0; i < (SZ); i++) re(a[i]);
}
}  // namespace __input
using namespace __input;
namespace __output {
template <class T1, class T2>
void pr(const pair<T1, T2>& x);
template <class T, size_t SZ>
void pr(const array<T, SZ>& x);
template <class T>
void pr(const vector<T>& x);
template <class T>
void pr(const deque<T>& x);
template <class T>
void pr(const set<T>& x);
template <class T1, class T2>
void pr(const map<T1, T2>& x);
template <class T>
void pr(const T& x) {
  cout << x;
}
template <class Arg, class... Args>
void pr(const Arg& first, const Args&... rest) {
  pr(first);
  pr(rest...);
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x) {
  pr("{", x.first, ", ", x.second, "}");
}
template <class T, bool pretty = true>
void prContain(const T& x) {
  if (pretty) pr("{");
  bool fst = 1;
  for (const auto& a : x) pr(!fst ? pretty ? ", " : " " : "", a), fst = 0;
  if (pretty) pr("}");
}
template <class T>
void pc(const T& x) {
  prContain<T, false>(x);
  pr("\n");
}
template <class T, size_t SZ>
void pr(const array<T, SZ>& x) {
  prContain(x);
}
template <class T>
void pr(const vector<T>& x) {
  prContain(x);
}
template <class T>
void pr(const deque<T>& x) {
  prContain(x);
}
template <class T>
void pr(const set<T>& x) {
  prContain(x);
}
template <class T1, class T2>
void pr(const map<T1, T2>& x) {
  prContain(x);
}
void ps() { pr("\n"); }
template <class Arg>
void ps(const Arg& first) {
  pr(first);
  ps();
}
template <class Arg, class... Args>
void ps(const Arg& first, const Args&... rest) {
  pr(first, " ");
  ps(rest...);
}
}  // namespace __output
using namespace __output;
namespace __algorithm {
template <typename T>
void dedup(vector<T>& v) {
  sort((v).begin(), (v).end());
  v.erase(unique((v).begin(), (v).end()), v.end());
}
template <typename T>
typename vector<T>::iterator find(vector<T>& v, const T& x) {
  auto it = lower_bound((v).begin(), (v).end(), x);
  return it != v.end() && *it == x ? it : v.end();
}
template <typename T>
size_t index(vector<T>& v, const T& x) {
  auto it = find(v, x);
  assert(it != v.end() && *it == x);
  return it - v.begin();
}
template <typename C, typename T, typename OP>
vector<T> prefixes(const C& v, T id, OP op) {
  vector<T> r(int((v).size()) + 1, id);
  for (int i = 0; i < (int((v).size())); i++) r[i + 1] = op(r[i], v[i]);
  return r;
}
template <typename C, typename T, typename OP>
vector<T> suffixes(const C& v, T id, OP op) {
  vector<T> r(int((v).size()) + 1, id);
  for (int i = (int((v).size())) - 1; i >= 0; i--) r[i] = op(v[i], r[i + 1]);
  return r;
}
}  // namespace __algorithm
using namespace __algorithm;
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-parameter"
struct monostate {
  friend istream& operator>>(istream& is, const monostate& ms) { return is; }
  friend ostream& operator<<(ostream& os, const monostate& ms) { return os; }
  friend monostate operator+(const monostate& a, const monostate& b) {
    return a;
  }
} ms;
#pragma GCC diagnostic pop
namespace __io {
void setIn(string second) { freopen(second.c_str(), "r", stdin); }
void setOut(string second) { freopen(second.c_str(), "w", stdout); }
void setIO(string second = "") {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(15);
  if (int((second).size())) {
    setIn(second + ".in"), setOut(second + ".out");
  }
}
}  // namespace __io
using namespace __io;
enum C_t { LEAF, SERIES, PARALLEL };
struct circuit {
  C_t type = LEAF;
  vector<circuit> elts = {};
  ll coeff = 1;
};
circuit parse(string inp) {
  if (inp == "*") return {};
  vector<circuit> res;
  for (auto& c : inp) {
    switch (c) {
      case '(':
        res.emplace_back();
        break;
      case 'P':
      case 'S':
        res.back().type = c == 'P' ? PARALLEL : SERIES;
        break;
      case '*':
        res.back().elts.emplace_back();
        break;
      case ')':
        if (int((res).size()) > 1) {
          res[int((res).size()) - 2].elts.push_back(move(res.back()));
          res.pop_back();
        }
      default:
        break;
    }
  }
  assert(int((res).size()) == 1);
  return res.back();
}
ll calc_coeff(circuit& c) {
  if (c.type == SERIES) {
    c.coeff = LLONG_MAX;
    for (auto& e : c.elts) ckmin(c.coeff, calc_coeff(e));
  }
  if (c.type == PARALLEL) {
    c.coeff = 0;
    for (auto& e : c.elts) c.coeff += calc_coeff(e);
  }
  return c.coeff;
}
vll output;
void assign(circuit& c, ll R) {
  if (c.type == LEAF) {
    output.push_back(R);
    return;
  }
  if (c.type == SERIES) {
    int mi = 0;
    for (int i = (1); i < (int((c.elts).size())); i++)
      if (c.elts[i].coeff < c.elts[mi].coeff) mi = i;
    for (int i = 0; i < (int((c.elts).size())); i++)
      assign(c.elts[i], i != mi ? 0ll : R);
  }
  if (c.type == PARALLEL) {
    for (auto& e : c.elts) assign(e, R);
  }
}
void solve() {
  string inp;
  getline(cin, inp);
  int sp = inp.find(' ');
  int R = atoi(inp.substr(0, sp).c_str());
  while (inp[sp] == ' ') sp++;
  circuit c = parse(inp.substr(sp));
  calc_coeff(c);
  assign(c, c.coeff * R);
  pr("REVOLTING "), pc(output);
  output.clear();
}
int main() {
  setIO();
  string _T;
  getline(cin, _T);
  int T;
  T = atoi(_T.c_str());
  for (int t = 0; t < (T); t++) {
    solve();
  }
  return 0;
}