410315: GYM104008 L Largest Unique Wins

L. Largest Unique Winstime limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard output

$$$n$$$ players are playing a game. They are to choose a number from $$$1, 2, \dots, m$$$ at the same time, and the game result should be analyzed as follows:

• If there exists a number that exactly $$$1$$$ player chooses, then the player with the largest such number wins and scores $$$1$$$ point; the other players score $$$-1$$$ point.
• Otherwise, the game is declared no winner; everyone is rewarded with a $$$0$$$ point.

The game plays only one round. To keep the game fair, the judge comes up with a new playing method for this game. Instead of giving a simple action, every player should submit their strategy to the judge, which should be a $$$m$$$-dimensional vector $$$s = (p_1, p_2, \dots, p_m)$$$, where $$$\sum_{i = 1} ^ m p_i = 1$$$ must hold. After that, the judge starts to roll the dice. For player $$$i$$$, the judge will sample a result uniformly at random according to $$$s_i$$$: with probability $$$s_{i, j}$$$, the number $$$j$$$ is chosen. After sampling $$$n$$$ numbers, the game concludes by the above rules.

The Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equilibrium strategies of the other players, and no one has anything to gain by changing only one's own strategy. To be more precise, we can define the term Nash Equilibrium on this game: given $$$n$$$ vectors of each player's strategy, if for each player, their strategy is the best response to the other players' strategies, we call it a Nash equilibrium. In other words, one can not earn a higher expected score in a Nash equilibrium by peeping at others' strategies and making some changes to their strategy.

Now, we'd like you to find a Nash equilibrium given $$$n$$$ and $$$m$$$. Note that you don't have to maximize or minimize anything related to scores, but you should guarantee that no one can take advantage by changing strategy on the spot.

Input

The only input line contains two integers $$$n, m\, (2 \leq n, m \leq 12)$$$, denoting that it's a game that involves $$$n$$$ players, and each player has to choose from $$$1 \dots m$$$.

Output

Print $$$n$$$ lines, each contains $$$m$$$ decimal numbers. The the $$$j$$$-th decimal number $$$s_{i, j}$$$ on $$$i$$$-th line means that player $$$i$$$ plays $$$j$$$ with probability $$$s_{i, j}$$$.

You should guarantee the following precision requirements:

• $$$\forall i \in \{1, \dots, n\}, \left|\sum_{j = 1}^{m} s_{i, j}-1\right| < 10 ^ {-8}.$$$
• $$$\forall i \in \{1, \dots, n\}$$$, replacing $$$s_i$$$ to another strategy $$$s'_i$$$ can not have a expected reward gain more than $$$10^{-8}$$$.

Printing $$$10$$$ or more digits after the decimal point is recommended to fulfill precision requirements.

Nash showed that there is always a Nash equilibrium for every finite game. If there are multiple solutions, print any.

ExamplesInput

2 2

Output

0.0000000000 1.0000000000
0.0000000000 1.0000000000

Input

3 3

Output

0.2360679775 0.2360679775 0.5278640450
0.2360679775 0.2360679775 0.5278640450
0.2360679775 0.2360679775 0.5278640450

Input

3 2

Output

1.0000000000 0.0000000000
0.0000000000 1.0000000000
0.1145141919 0.8854858081

Note

The reference outputs for the first and the second sample are symmetric, meaning that every player uses the same strategy. We can prove that the reference output is the only Nash equilibrium in the first sample. However, asymmetric solutions exist for the second sample — even if players take different strategies, no one has the incentive to change their own given that the other players stick to their previous choice.

In the third sample case, we present an asymmetric example for you. The most interesting thing about it is viewing from the player $$$3$$$'s aspect. Fixing $$$1, 2$$$'s strategy,

• If player $$$3$$$ chooses $$$1$$$, player $$$2$$$ wins.
• If player $$$3$$$ chooses $$$2$$$, player $$$1$$$ wins.

Therefore, player $$$3$$$'s revenue is always the same, $$$-1$$$. However, $$$3$$$'s strategy can decide who wins for players $$$1$$$ and $$$2$$$. It can also be verified that player $$$1, 2$$$ have no incentive to change strategies too due to the existence of player $$$3$$$.