405911: GYM102156 B Unfair Card Deck

In yet another card game, there are several types of cards and a deck of 30 cards. For each card type, there is either a single card of that type in the deck or two such cards. Initially, the deck is shuffled. Afterwards, the cards are drawn randomly from the deck one by one until it is empty.

Having played $$$100\,000$$$ games, you noticed that the dealer draws the cards unfairly. Instead of picking the next card randomly, he follows some strange algorithm. The $$$i$$$-th card type is assigned a weight $$$X_i$$$ ($$$0 < X_i \leq 1$$$). On every turn, the probability that the next drawn card would be of type $$$i$$$ is $$$c_i X_i / S$$$, where $$$c_i$$$ is the number of remaining cards of the $$$i$$$-th type and $$$S = \sum\limits_{j} c_j X_j$$$ is the sum of weights of all remaining cards.

In order to be prepared for the next playing session, you want to be able to predict the actions of the dealer. Fortunately, you remember the order in which the cards were drawn in all $$$100\,000$$$ games. Given that information, find the weight assigned to each card type.

In the first line, there are two integers $$$m$$$ and $$$n$$$ ($$$m = 100\,000$$$, $$$1 \leq n \leq 30$$$), the number of games and the number of card types.

In the next line, there are $$$n$$$ integers $$$a_1$$$, ..., $$$a_n$$$ ($$$1 \leq a_1 \leq 2$$$, $$$\sum\limits_{i=1}^{n} a_i = 30$$$), denoting how many cards of the $$$i$$$-th type are there in the deck.

Each of the next $$$m$$$ lines contains the log of a single game. The log consists of $$$30$$$ numbers: the types of the cards in the order they were drawn. For each $$$1 \leq i \leq n$$$, the number $$$i$$$ occurs in the log exactly $$$a_i$$$ times.

Print $$$n$$$ numbers $$$W_1$$$, ..., $$$W_n$$$ ($$$10^{-300} < W_i \leq 1$$$), the predicted weights of the card types. The answer will be considered correct if, for each pair of types $$$i$$$ and $$$j$$$ such that $$$X_i \leq X_j$$$, the following holds:

$$$$$$\left|\frac{X_i}{X_i + X_j} - \frac{W_i}{W_i + W_j}\right| < 0.02$$$$$$

Small input example (note that it will not occur in the testset, since $$$m$$$ is always $$$100\,000$$$):

4 3 2 1 1 1 1 2 3 1 2 1 3 1 2 3 1 2 1 1 3