Decision and Strategy are master programmers.

It is time for lunch, but Decision and Strategy do not have time to eat, so they decide to choose one person to go get food.

Strategy suggests using Rock-Paper-Scissors to decide the winner, but Decision feels this lacks technical depth and cannot lead to interesting decisions. He proposes a small game to decide the winner:

1. Both sides have an energy bar that can store at most $n$ energy.
2. Both sides have a "super skill." When the energy bar is full, they can release the super skill, consuming all energy.
3. Besides the super skill, there are $m$ types of small skills, numbered $1, \dots, m$, divided into three categories:
   1. Consumption type: Consumes $x$ energy; can only be used if current energy is at least $x$.
   2. Free type: Consumes no energy; can be used at any time.
   3. Supply type: Grants $x$ energy upon use; if the total energy exceeds $n$ after use, the excess is wasted. Can be used at any time.
4. There are relationships of mutual restraint between skills. The super skill restrains all small skills. The game defines several restraint relationships between small skills, each in the form: skill $i$ restrains skill $j$. There are no restraint relationships between other skills.
5. Each turn, both players must choose a usable skill and reveal them simultaneously. If one player's skill restrains the other's, the game ends and that player wins. Otherwise, both players update their energy bars and continue the game. If both players use the super skill simultaneously, both empty their energy bars and continue the game.
6. If the game never ends, it is counted as $0.5$ wins for each player.

Decision discovers that he can use an AI to play against Strategy, so he doesn't have to spend effort playing himself.

Decision also finds that the optimal strategy for each game state depends only on the energy bars of both sides. Therefore, he only needs to provide the program with a strategy table recording the probability of using each skill in every state.

However, Strategy is very strategic. Decision knows that Strategy will sneak into his computer to peek at his program and strategy table. But because Decision uses the current system time as a random seed, Strategy cannot know exactly what will be played this time, only the probability of each skill being used.

Now Decision has found you. Please find a strategy such that your win rate is at least $50\%$.

At the same time, Strategy has also found you. He has given you Decision's strategy table. Please find a strategy that maximizes the win rate.

Meanwhile, Xi has also found you. He has provided the strategy tables for both people and would like you to calculate the win rate for each person.

Strategy Table Input/Output Format

Each energy bar has $n + 1$ states, so there are $(n + 1)^2$ game states. Obviously, if someone's energy bar is full, they will definitely use the super skill, so the strategy table only needs to record the strategies for $n^2$ states.

There are $n^2$ lines in total. The $i$-th line (0-indexed) represents the strategy when your energy is $\lfloor \frac{i}{n} \rfloor$ and the opponent's energy is $i \bmod n$.

Each strategy occupies one line, containing $m$ integers, representing the probability of using small skills $1, \dots, m$ multiplied by $10^9$. It is guaranteed that these numbers sum to $10^9$, and the probability of using currently unusable small skills (e.g., certain consumption types) is $0$.

Input

Multiple test cases. The first line contains the test point number, the number of test cases $\mathrm{Case}$, and the data type $\mathrm{type}$.

For each test case, the first line contains two positive integers representing the energy bar limit $n$ and the number of small skill types $m$.

If $\mathrm{type}=1$, you need to solve Xi's query. If $\mathrm{type}=2$, you need to solve Strategy's query. If $\mathrm{type}=3$, you need to solve Decision's query.

The next line contains $m$ integers $v_1, \dots, v_m$, representing the change in energy for each small skill, i.e., the user's energy increases by $v_i$ after use. $v_i < 0$ indicates a consumption type, $v_i = 0$ indicates a free type, and $v_i > 0$ indicates a supply type.

The next $m$ lines each contain $m$ integers. If the element at row $i$, column $j$ is $1$, it means skill $i$ restrains skill $j$. If it is $-1$, it means skill $j$ restrains skill $i$. If it is $0$, there is no restraint relationship. It is guaranteed that diagonal elements are $0$ and the element at row $i$, column $j$ is the negative of the element at row $j$, column $i$.

If $\mathrm{type} \neq 3$, the next $n^2$ lines are Decision's strategy table.

If $\mathrm{type} = 1$, the next $n^2$ lines are Strategy's strategy table.

Output

If $\mathrm{type} = 1$, output a single floating-point number representing Decision's win rate. An absolute error within $10^{-6}$ of the standard answer is considered correct.

If $\mathrm{type} = 2$, output a strategy table. Let the win rate of this strategy table against Decision's strategy table be $x$, and the win rate of our reference solution be $y$. If $x > y - 10^{-6}$, it is considered correct.

If $\mathrm{type} = 3$, output a strategy table. We will generate a strategy table. Let the win rate of your strategy table against our strategy table be $x$. If $x > 0.5 - 10^{-6}$, it is considered correct.

Note: During evaluation, to prevent precision errors, if a state has less than $10^{-8}$ probability of transitioning into an infinite loop, the win rate for that state is set directly to $0.5$.

Examples

Input 1

0 1 1
2 3
-1 0 1
0 0 1
0 0 0
-1 0 0
0 0 1000000000
0 1000000000 0
0 0 1000000000
333333334 333333333 333333333
0 0 1000000000
0 1000000000 0
0 0 1000000000
333333334 333333333 333333333

Output 1

0.5000000000

Input 2

0 1 2
2 3
-1 0 1
0 0 1
0 0 0
-1 0 0
0 0 1000000000
0 1000000000 0
0 0 1000000000
333333334 333333333 333333333

Output 2

0 0 1000000000
0 1000000000 0
0 0 1000000000
333333334 333333333 333333333

Input 3

0 1 3
2 3
-1 0 1
0 0 1
0 0 0
-1 0 0

Output 3

0 0 1000000000
0 1000000000 0
0 0 1000000000
333333334 333333333 333333333

Constraints

Except for test points 5 and 6, all data is randomly generated.

Random generation method:

• For each skill, there is a $1/3$ probability of being free type, $1/3$ consumption type, and $1/3$ supply type. The absolute value of $x$ for consumption and supply types does not exceed $3$.
• It is guaranteed that at least one of each of the three types exists.
• Generation of restraint relationships between small skills:
  • For each pair of skills, there is a $20\%$ probability of a restraint relationship:
    • If the energy loss after use is the same, each has a $50\%$ probability of restraining the other.
    • If the energy loss is different, the one with the higher gain has a $20\%$ probability of restraining the other, and the one with the lower gain has an $80\%$ probability of restraining the other.
    • It is guaranteed that every supply-type skill is restrained by at least one skill.
  • It is guaranteed that there exists at least one supply-type skill that is only restrained by consumption-type skills.
• Strategy table generation method:
  • For a state, set the usage probabilities of usable small skills to be equal. Since it must be an integer multiple of $10^{-9}$, it may not be possible to distribute them perfectly evenly; it is guaranteed that the absolute difference between the usage probabilities of any two usable small skills does not exceed $10^{-9}$.
  • Then perform $100$ operations. Each operation selects two different usable small skills $i$ and $j$, generates a uniform random number $\delta$ between $10^{-9}$ and the usage probability of skill $i$, where $\delta$ is an integer multiple of $10^{-9}$. Decrease the probability of $i$ by $\delta$ and increase the probability of $j$ by $\delta$.

If you do not understand, you can refer to test point 1.

Time limit: $2\texttt{s}$

Memory limit: $256\texttt{MB}$