18515번 - 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 ≤ 1). On every turn, the probability that the next drawn card would be of type i is c_iX_i/S, where c_i is the number of remaining cards of the i-th type and S = Σ_jc_jX_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 100 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 ≤ n ≤ 30), the number of games and the number of card types.

In the next line, there are n integers a₁, . . . , a_n (1 ≤ a₁ ≤ 2, Σ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 ≤ i ≤ n, the number i occurs in the log exactly ai times.

Print n numbers W₁, . . . , W_n (10⁻³⁰⁰ < W_i ≤ 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 ≤ 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):