给定一个整数数组$$$s_1, s_2, \ldots, s_l$$$,每一秒,宇宙射线都会导致所有$$$s_i$$$同时被删除,使得$$$i=1$$$或$$$s_i\neq s_{i-1}$$$被同时删除,剩下的部分将被连接在一起以形成新的数组$$$s_1、s_2、\ldots、s_{l'}$$$。
将数组的强度定义为变空所需的秒数。
给您一个以 $$$n$$$ 对的形式压缩的整数数组,这些对从左到右描述该数组。每对 $$$(a_i,b_i)$$$ 代表 $$$a_i$$$ 的 $$$b_i$$$ 副本,即 $$$\underbrace{b_i,b_i,\cdots,b_i}_{a_i\textrm{ times}}$$$。
对于每个 $$$i=1,2,\dots,n$$$,请找出前 $$$i$$$ 对描述的序列的强度。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1\le t\le10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le3\cdot10^5$$$) — 序列 $$$a$$$ 的长度。
接下来的 $$$n$$$ 行包含两个整数,每个 $$$a_i$$$, $$$b_i$$$ ($$$1\le a_i\le10^9,0\le b_i\le n$$$) - 描述序列的对。
保证所有$$$n$$$的总和不超过$$$3\cdot10^5$$$。
保证对于所有 $$$1\le i<n$$$,$$$b_i\neq b_{i+1}$$$ 成立。
输出
对于每个测试用例,打印一行包含 $$$n$$$ 整数 - 每个前缀对的答案。
示例
输入 #1
4 4 2 0 1 1 3 0 5 1 6 4 6 1 3 4 6 4 0 7 6 6 3 7 9 0 7 1 5 0 7 1 9 0 1 1 2 0 10 10 7 4 9 2 2 7 9 2 8 8 5 11 7 15 5 12 7 4 0
输出 #1
2 2 4 5 4 4 7 7 10 10 9 9 9 9 9 9 10 10 10 10 10 10 10 12 15 15 15
注意
在第一个测试用例中,对于长度 $$$4$$$ 的前缀,更改将为 $$$[0,0,1,0,0,0,1,1,1,1,1]\rightarrow[0,0,0,1,1,1,1]\rightarrow[0,0,1,1,1]\rightarrow[0,1,1]\rightarrow[1]\rightarrow[]$$$,因此数组在 $$$5$$$ 秒后变空。
在第二个测试用例中,对于长度 $$$4$$$ 的前缀,更改将为$$$[6,6,6,6,3,6,6,6,6,0,0,0,0]\rightarrow[6,6,6,6,6,6,0,0,0]\rightarrow[6,6,6,6,6,0,0]\rightarrow[6,6,6,6,0]\rightarrow[6,6,6]\rightarrow[6,6]\rightarrow[6]\rightarrow[]$$$,所以$$$7$$$ 秒后数组变空。