I. Inés and her compitas
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Inés regularly plays her favorite game: "Don't compete, make compitas". This game is played in rounds, and in each round, players must choose between two options:

  • Option $$$1$$$: Share $$$X$$$ units of gold among the players who choose this option (rounding down). That is, if $$$k$$$ players choose this option, each receives $$$\left\lfloor {\frac{X}{k}} \right\rfloor$$$ units of gold.
  • Option $$$2$$$: Receive $$$Y$$$ units of gold directly, without sharing.

Inés will play with $$$N$$$ other players in a game of $$$M$$$ rounds. She knows in advance which option each of the other players will choose in each round. With this information, she wants to decide her strategy to maximize the gold she receives in each round.

Your task is to help Inés make the best decision in each round to achieve her goal, and also, determine the total gold that each player will receive. In case both options in a round are equally convenient for Inés, she will choose option $$$1$$$ (sharing), as she finds it the more fun option.

Note: $$$\left\lfloor {x} \right\rfloor$$$ is the largest integer that is less than or equal to $$$x$$$. For example, $$$\left\lfloor {2.5} \right\rfloor = 2$$$, $$$\left\lfloor {\pi} \right\rfloor = 3$$$, and $$$\left\lfloor {5} \right\rfloor = 5$$$.

Input

A line with two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N, M \leq 100$$$), which indicate respectively the number of players playing with Inés and the number of rounds. Each player playing with Inés is identified by a distinct integer between $$$1$$$ and $$$N$$$.

The following $$$2M$$$ lines describe the rounds, using two consecutive lines per round.

The first line of each round contains two integers $$$X$$$ and $$$Y$$$ ($$$1 \leq X, Y \leq 10^5$$$), which indicate respectively the amount of gold for options $$$1$$$ and $$$2$$$ in that round.

The second line of each round contains $$$N$$$ integers $$${A_1}, {A_2}, \ldots, {A_N}$$$ ($$$A_i=1$$$ or $$$A_i=2$$$), indicating that player $$$i$$$ chooses option $$$A_i$$$ in that round.

Output

A single line with $$$N+1$$$ integers, representing the total gold received by each of the players (including Inés) if Inés decides her strategy as explained. The first $$$N$$$ integers represent the gold of each of the $$$N$$$ players (excluding Inés), ordered by player, while the last integer represents Inés's gold.

Example
Input
3 3
15 10
1 2 1
13 8
2 2 2
16 4
1 1 1
Output
19 22 19 27
Note

Let's see what Inés can do in the example:

  • Round 1:
    • If Inés chose option $$$1$$$, there would be $$$k=3$$$ players choosing that option (players $$$1$$$ and $$$3$$$, along with Inés herself). Each of them would receive $$$\left\lfloor {\frac{X}{k}} \right\rfloor=\left\lfloor {\frac{15}{3}} \right\rfloor=5$$$ units of gold.
    • If Inés chose option $$$2$$$, she would receive $$$Y=10$$$ units of gold.
    • Therefore, Inés chooses option $$$2$$$.
  • Round 2:
    • If Inés chose option $$$1$$$, she would receive $$$\left\lfloor {\frac{13}{1}} \right\rfloor=13$$$ units of gold.
    • If Inés chose option $$$2$$$, she would receive $$$8$$$ units of gold.
    • Therefore, Inés chooses option $$$1$$$.
  • Round 3:
    • If Inés chose option $$$1$$$, she would receive $$$\left\lfloor {\frac{16}{4}} \right\rfloor=4$$$ units of gold.
    • If Inés chose option $$$2$$$, she would receive $$$4$$$ units of gold.
    • Both options yield the same benefit for her, but she finds sharing more fun. Therefore, Inés chooses option $$$1$$$.
In total, Inés receives $$$10 + 13 + 4 = 27$$$ units of gold.

Now let's see how much gold player $$$1$$$ receives:

  • Round 1: Chooses option $$$1$$$. Since Inés chooses option $$$2$$$, there are $$$k=2$$$ players choosing option $$$1$$$ (players $$$1$$$ and $$$3$$$). Each of them receives $$$\left\lfloor {\frac{X}{k}} \right\rfloor=\left\lfloor {\frac{15}{2}} \right\rfloor=7$$$ units of gold.
  • Round 2: Chooses option $$$2$$$. Therefore, he receives $$$Y=8$$$ units of gold.
  • Round 3: Chooses option $$$1$$$. Since Inés also chooses option $$$1$$$, ultimately all four players choose this same option. Each of them receives $$$\left\lfloor {\frac{16}{4}} \right\rfloor=4$$$ units of gold.

In total, player $$$1$$$ receives $$$7 + 8 + 4 = 19$$$ units of gold.