E. Космические лучи
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив целых чисел $$$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{ раз}}$$$.

Для каждого $$$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$$$ целых чисел — ответ для каждого префикса пар.

Пример
Входные данные
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
Выходные данные
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$$$ секунд.