题目描述

考虑两位玩家进行如下的一个信任游戏（请注意，这个游戏可能与你所了解的某游戏有所不同）：

• 有一台这样的机器：当一位玩家放进去一枚硬币，另一位玩家会得到三枚硬币。
• 游戏共进行 $2m$ 轮，两位玩家轮流行动，每次行动中，行动的玩家可以选择一下两种操作其一：
  • 「合作」：放入一枚硬币；
  • 「欺骗」：不放硬币。
• 若选择「合作」，则行动的玩家失去一枚硬币，另一位玩家获得三枚硬币；若选择「欺骗」，则无事发生。
• 每次行动后，另一位玩家会获知当前行动玩家的选择。

现在你将和「复读机」进行这个信任游戏，你先行动。「复读机」的策略可以用若干个长度不超过 $m$ 的 $01$ 串构成的可重集合 $S$ 表示。他的具体策略为：先从集合中等概率随机选取一个 $01$ 串 $s$，设其长度为 $k$，则他在第 $2i$ $(1 \le i \le m)$ 轮（也就是他的第 $i$ 次行动）时策略为：

• 对于 $1 \le i \le k$，若 $s_i = 0$，则选择「合作」；若 $s_i = 1$，选择「欺骗」。
• 对于 $k < i \le m$，选择与你的上一次选择相同，也就是第 $2i-1$ 轮的选择。

现在你的对手「复读机」的策略池 $S$ 还未确定，他会进行 $n$ 次操作：每次操作包含一个长度不超过 $m$ 的 $01$ 串 $s_i$ 和数量 $a_i$，表示向 $S$ 中加入 $a_i$ 个 $s_i$。特别地，如果 $a_i < 0$，则表示从 $S$ 中删除 $-a_i$ 个 $s_i$，其中 $S$ 中至少有 $-a_i$ 个 $s_i$，且删除后 $S$ 中至少还有 $1$ 个 $01$ 串。

你需要在每次操作后，计算出你在最优策略下，期望最多收益为多少硬币，每次操作后的询问相互独立。请注意，你已知集合 $S$，但你并不能得知他选择的 $01$ 串 $s$，而你的每次行动都可以基于之前轮双方的选择进行决策。你只需要输出期望收益乘 $|S|$ 的值，可以证明是一个整数。

输入格式

从标准输入读入数据。

输入的第一行包含两个正整数 $n, m$。

输入的第 $i+1$ $(1 \le i \le n)$ 包含一个长度不超过 $m$ 的 $01$ 串 $s_i$ 和一个整数 $a_i$。

输出格式

输出到标准输出。

输出 $n$ 行，每行一个整数表示答案。

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

0
3
10
18
15
28
22
41

子任务

对于所有测试数据，均有：

• $1 \le n \le 3 \times 10^5$，$1 \le m \le 10^6$；
• 对于所有 $1 \le i \le n$，均有 $1 \le |s_i| \le m$，$1 \le |a_i| \le 10^6$，且 $\sum_{i=1}^{n} |s_i| \le 4 \times 10^5$。
• 对于所有 $1 \le i \le n$，若 $a_i < 0$，则 $S$ 中至少有 $-a_i$ 个 $s_i$，且删除后 $S$ 中至少还有 $1$ 个 $01$ 串。

特殊性质 A：对于所有 $1 \le i \le n$，均有 $a_i = 1$，且 $\sum_{i=1}^{n} |s_i| \le 5000$。

特殊性质 B：对于所有 $1 \le i < n$，均有 $|s_i| \ge |s_{i+1}|$。

评分方式

对于每个子任务：

1. 正确回答所有测试数据的第 $n$ 次操作后的答案，可获得该子任务 $40\%$ 的分数；
2. 正确回答所有测试数据的答案，可获得该子任务 $100\%$ 的分数。

注意：即使选手仅回答了第 $n$ 次操作后的答案，也需要按照输出格式输出 $n$ 个整数，分别对应每次操作后的答案。