CF1280E.Kirchhoff's Current Loss

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.

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, \ldots, R_k$, the effective resistance $R$ of the resulting circuit is the sum $$R = R_1 + R_2 + \ldots + R_k.$$

• When joining $k$ circuits in parallel with effective resistances $R_1, R_2, \ldots, R_k$, the effective resistance $R$ of the resulting circuit is found by solving for $R$ in $$\frac{1}{R} = \frac{1}{R_1} + \frac{1}{R_2} + \ldots + \frac{1}{R_k},$$ assuming all $R_i \gt 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, \ldots, s_k$ represent $k \ge 2$ circuits. Then:

• "($s_1$ S $s_2$ S $\ldots$ S $s_k$)" represents their series circuit;
• "($s_1$ P $s_2$ P $\ldots$ P $s_k$)" represents their parallel circuit.

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

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, \ldots, r_n$ ($0 \le 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}$.

你的朋友基尔霍夫对当前电子电路设计的现状感到震惊。

“天哪！这行当到底怎么了？所有这些电路都效率低下！还有巨大的改进空间。电气工程师们一定没把课教好。简直令人作呕！”他说道。

负面情绪持续从他身上倾泻而出，然而即便抱怨了无数次，他仍未能获得直接改变现状的机会。

“这些电路的总电阻太大了！他们为何要这样布线？这只会造成大量电阻器的浪费！只要充分挖掘设计潜力，整个领域本可以节省巨额资金。他们为何不尝试一些替代方案呢？”

他对电气工程系的抗议频率之高，令你灵魂震颤（hertz your soul），因此你决定挺身而出，亲自出手相助。你计划编写一个程序，在保持原有电路拓扑结构不变的前提下，优化电路参数，同时维持其等效电阻恒定。

一个电路具有两个端点，并关联一个称为其等效电阻的常数 $R$。

我们所考虑的电路由单个电阻器通过串联或并联方式连接而成，从而构成更复杂的电路。下图展示了电路的串联与并联组合方式：

据你朋友基尔霍夫所述，以这种方式组合电路时，其等效电阻可非常简便地计算：

• 当将 $k$ 个等效电阻分别为 $R_1, R_2, \ldots, R_k$ 的电路串联时，所得电路的等效电阻 $R$ 为各电阻之和：

  $$R = R\_1 + R\_2 + \\ldots + R\_k.$$

• 当将 $k$ 个等效电阻分别为 $R_1, R_2, \ldots, R_k$ 的电路并联时，所得电路的等效电阻 $R$ 满足：

  $$\\frac{1}{R} = \\frac{1}{R\_1} + \\frac{1}{R\_2} + \\ldots + \\frac{1}{R\_k},$$

  其中假设所有 $R_i > 0$；若至少有一个 $R_i = 0$，则整个电路的等效电阻即为 $R = 0$。

电路将用字符串表示。单个电阻器用星号 “*” 表示。对于更复杂的电路，设 $s_1, s_2, \ldots, s_k$ 表示 $k \ge 2$ 个电路，则：

• “($s_1$ S $s_2$ S $\ldots$ S $s_k$)” 表示它们的串联电路；
• “($s_1$ P $s_2$ P $\ldots$ P $s_k$)” 表示它们的并联电路。

例如，“(* P (* S *) P *)” 表示如下电路：

给定一个电路，你的任务是为每个单个电阻器分配阻值，使其满足以下要求：

• 每个单个电阻器的阻值为非负整数；
• 整个电路的等效电阻恰好为 $r$；
• 所有单个电阻器阻值之和最小。

若电路中共有 $n$ 个单个电阻器，则你需要输出列表 $r_1, r_2, \ldots, r_n$（其中 $0 \le r_i$，且 $r_i$ 为整数），其中 $r_i$ 表示输入字符串中从左至右第 $i$ 个出现的单个电阻器所分配的阻值。若该任务无法实现，你也必须明确指出。

若任务可行，则保证最小总阻值不超过 $10^{18}$。

The first line of input contains a single integer $t$ ($1 \le t \le 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 \le r \le 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$.

输入的第一行包含一个整数 $t$（$1 \le t \le 32000$），表示测试用例的数量。接下来的若干行包含各测试用例的描述。

每个测试用例由一行组成，该行包含一个整数 $r$（$1 \le r \le 10^6$），后跟一个空格，再跟一个表示电路的字符串。保证该字符串是合法的，并符合上述描述。单个电阻器（符号“*”）的数量至少为 $1$，至多为 $80000$。

保证所有测试用例中单个电阻器的总数不超过 $320000$。

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, \ldots, 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).

对于每个测试用例，输出一行：

• 如果可以实现等效电阻 $r$，则输出 "REVOLTING"（不带引号），随后输出 $n$ 个整数 $r_1, r_2, \ldots, r_n$ —— 即分配给各个电阻器的阻值。其中，$n$ 表示电路中单个电阻器的数量。

  可能存在多种满足条件的分配方案，且使得各电阻器阻值之和最小；您可输出其中任意一种；

• 如果不可能实现，则输出字符串 "LOSS"（不带引号）。

The following illustrates the third sample case:

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.

下图展示了第三个样例：

此处，各电阻器的阻值之和为 $2 + 1 + 1 = 4$，可证明该值为最小值。注意，可能存在其他分配方案也能达到这一最小值。