Consider two players participating in a trust game (note that this trust game may differ from others you are familiar with):

• There is a machine such that when one player puts in one coin, the other player receives three coins.
• The game lasts for $2m$ rounds, with the two players taking turns. In each turn, the acting player can choose one of the following two operations:
  • "Cooperate": Put in one coin.
  • "Defect": Do not put in a coin.
• If "Cooperate" is chosen, the acting player loses one coin, and the other player receives three coins; if "Defect" is chosen, nothing happens.
• After each action, the other player is informed of the current acting player's choice.

You are now playing this trust game against a "Repeater," and you move first. The strategy of the "Repeater" can be represented by a multiset $S$ consisting of several binary strings of length at most $m$. Its specific strategy is: first, it chooses a binary string $s$ from the set $S$ uniformly at random. Let its length be $k$. Then, in its $i$-th turn (which corresponds to the $2i$-th round of the game, for $1 \le i \le m$), its strategy is: For $1 \le i \le k$, if $s_i = 0$, it chooses "Cooperate"; if $s_i = 1$, it chooses "Defect". For $k < i \le m$, it chooses the same action as your previous move, which is your choice in the $(2i-1)$-th round.

The strategy pool $S$ of your opponent, the "Repeater," is not yet fixed. It will perform $n$ operations: each operation includes a binary string $s_i$ of length at most $m$ and a quantity $a_i$, representing the addition of $a_i$ copies of $s_i$ to $S$. Specifically, if $a_i < 0$, it means removing $-a_i$ copies of $s_i$ from $S$, where $S$ contains at least $-a_i$ copies of $s_i$, and after the removal, $S$ still contains at least one binary string.

After each operation, you need to calculate the maximum expected number of coins you can gain under an optimal strategy. The queries after each operation are independent. Note that you know the set $S$, but you do not know which binary string $s$ the opponent has chosen. However, each of your actions can be based on the choices made by both sides in previous rounds. You only need to output the value of the expected gain multiplied by $|S|$, which can be proven to be an integer.

Input

The input is read from standard input. The first line contains two positive integers $n, m$. The $(i+1)$-th line ($1 \le i \le n$) contains a binary string $s_i$ of length at most $m$ and an integer $a_i$.

Output

Output to standard output. Output $n$ lines, each containing an integer representing the answer.

Constraints

For all test data: $1 \le n \le 3 \times 10^5$, $1 \le m \le 10^6$; For all $1 \le i \le n$, $1 \le |s_i| \le m$, $1 \le |a_i| \le 10^6$, and $\sum_{i=1}^n |s_i| \le 4 \times 10^5$. * For all $1 \le i \le n$, if $a_i < 0$, then $S$ contains at least $-a_i$ copies of $s_i$, and after removal, $S$ still contains at least one binary string.

Special Property A: For all $1 \le i \le n$, $a_i = 1$, and $\sum_{i=1}^n |s_i| \le 5000$. Special Property B: For all $1 \le i < n$, $|s_i| \ge |s_{i+1}|$.

Scoring

For each subtask: 1. Correctly answering the result after the $n$-th operation for all test data earns 40% of the subtask's score. 2. Correctly answering the results for all operations for all test data earns 100% of the subtask's score.

Note: Even if you only answer the result after the $n$-th operation, you must still output $n$ integers according to the output format, corresponding to the answers after each operation.

Examples

Input 1

8 3
111 1
1 1
0 1
011 4
1 -1
01 3
011 -3
0 3

Output 1

0
3
10
18
15
28
22
41