D. Deductive Snooker Scoring
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Billiards is a sport where players use a cue to strike the white cue ball and pot other balls into pockets. One famous variant is Snooker. With Zhao Xintong winning the Snooker World Championship, this sport has gained more attention in China. The rules of Snooker are quite complex, and this problem focuses primarily on the scoring rules. Note that the Snooker rules described here may differ from actual Snooker rules, so please follow the description here.

First, let's familiarize ourselves with the $$$21$$$ balls in Snooker. Red balls: Each worth $$$1$$$ point, with $$$15$$$ balls in total. Colored balls: yellow ($$$2$$$ points), green ($$$3$$$ points), brown ($$$4$$$ points), blue ($$$5$$$ points), pink ($$$6$$$ points), black ($$$7$$$ points), with only one ball of each color.

We refer to the two players in a frame of Snooker as Player A and Player B. Both start with a score of $$$0$$$. Player A takes the first turn, and the process begins as follows:

  1. If red balls are present, the current player must first pot a red ball. If successful, add one point to his score and proceed to step 2; if unsuccessful, switch to the opponent who starts from step 1. If there are no red balls left on the table, proceed to step 3.
  2. After potting a red ball, the current player should select any one of the six colored balls and pot it. If successful, add the corresponding points of the colored ball to his score, then put the potted colored ball back on the table (this is the only case where a potted ball is returned to the table; in all other cases, potted balls are not returned to the table), then return to step 1; if unsuccessful, switch to the opponent who starts from step 1. Note that this step must be completed after potting a red ball, even if that red ball was the last one on the table.
  3. If there are no red balls left on the table, proceed to the color clearance phase. The current player must pot the colored ball with the lowest point remaining on the table. If successful, add the corresponding points to his score and continue with step 3; if unsuccessful, switch to the opponent who starts from step 1 (though in practice, it would directly jump to step 3). If no balls remain on the table, the frame ends.

For convenience, this problem does not consider any fouls or special situations, including but not limited to potting multiple balls simultaneously or potting non-target balls. Only the scenarios mentioned above need to be considered.

Due to overtime work, Panda missed the beginning of a Snooker frame. When he returns home and turns on the TV, he sees that a player is currently at the table. At this moment, there are $$$n$$$ balls (red and colored) on the table, where any balls that should be returned to the table have been put back, and the current scores of Players A and B are $$$a:b$$$. Panda wants to deduce what might have happened earlier based on the current situation. Specifically, output any sequence of successful and failed shots (encoded as output format described below) that could lead from the start of the frame to the given current state, or determine that no such sequence exists. If multiple solutions exist, output any one of them.

Input

The first line contains an integer $$$T$$$ ($$$1 \le T \le 2000$$$), indicating the number of test cases.

Each of the next $$$T$$$ lines contains four integers $$$a, b, n, p$$$ ($$$0 \le a, b \le 200$$$, $$$0 \le n \le 21$$$, $$$0 \le p \le 1$$$), representing the current scores of Player A and Player B as $$$a:b$$$, and the total number of red and colored balls currently on the table is $$$n$$$. If $$$p = 0$$$, Player A is currently at the table; if $$$p = 1$$$, Player B is currently at the table.

Output

For each test case, output a string representing the sequence of steps, where digits $$$\texttt{1}$$$ to $$$\texttt{7}$$$ indicate that the current player potted a ball of the corresponding points, and the character $$$\texttt{/}$$$ indicates that the player failed to pot a ball, resulting in a switch to the opponent. If no valid sequence exists, output $$$\texttt{NA}$$$ in a single line. If multiple solutions exist, output any one of them. The length of the output string for each test case should not exceed $$$100$$$. Do not output extra spaces.

Example
Input
7
8 110 1 1
147 0 0 0
0 0 21 0
1 0 20 0
1 1 19 1
0 0 0 0
147 0 0 1
Output
/16121516/17/1717171717171217121423456
171717171717171717171717171717234567

//1//
/1/1/
NA
NA
Note

The first test case in the example is the final frame where Zhao Xintong won the Snooker World Championship (Player A is Mark Williams, Player B is Zhao Xintong).