32421번 - Bingo for the Win! 스페셜 저지다국어

문제

Bingo is a game of chance for multiple players. Each player receives a sheet with some numbers, and a game master then calls out these numbers in a random order. Players cross off the numbers that they have heard, and the first player to cross off all their numbers wins the game. This basic version of the game has a reputation for being, well, a bit sedate. No particular action is required of the players except for not falling asleep.

In this problem we will analyze a more dynamic version of Bingo that requires quick thinking. In our version, called Speed Bingo, the game master also calls out the numbers from the sheets in a random order. However, whenever a number is called out, only the first player to signal that he or she has the number is allowed to cross it off their sheet. If a player has the same number multiple times, only one copy may be crossed off at a time. When multiple players have the same number(s) on their sheets, whoever has the fastest reaction time has an advantage in winning Speed Bingo. But how big an advantage? That’s what we need your help to find out.

Formally, there are $n$ players, each receiving a (possibly) different sheet of $k$ (not necessarily distinct) numbers. Player 1ドル$ is faster to react than player 2ドル,ドル who in turn is faster than player 3ドル,ドル and so on, with player $n$ being the slowest. Consider the following example, corresponding to the first sample input, where three players receive four numbers each:

When number “1” is called for the first time, player 1ドル$—being faster—will get to cross it off their sheet. The second time “1” is called, player 2ドル$ will get to cross it off. So on average, we would expect player 1ドル$ to do better than players 2ドル$ and 3ドル,ドル since both of them will need some numbers that player 1ドル$ will get to first. However, since players 2ドル$ and 3ドル$ have no numbers in common, their performances will be independent of each other, even though player 2ドル$ is faster than player 3ドル$.

Suppose the game is played until all players have crossed off all of their numbers, that is, until all $n \cdot k$ numbers on all of the sheets (including appropriate repetitions) have been read. Assuming the order of the numbers is uniformly random, how likely is it for each player to finish last?

입력

The input describes a single game of Speed Bingo. The first line contains two integers $n$ and $k,ドル the number of players and number of numbers on each sheet (1ドル ≤ n ≤ 100,ドル 1ドル ≤ k ≤ 1,円 000$). This is followed by $n$ lines containing $k$ integers each, where the $i$th line gives the numbers on the sheet for the $i$th player. All those numbers are between 1ドル$ and 10ドル^9,ドル inclusive.

출력

Output $n$ lines, one for each player. The $i$th line should contain the probability that player $i$ finishes last. All values must be accurate to an absolute error of at most 10ドル^{-6}$.

제한

힌트