CF1916C Training Before the Olympiad

Masha and Olya have an important team olympiad coming up soon. In honor of this, Masha, for warm-up, suggested playing a game with Olya: There is an array $ a $ of size $ n $ . Masha goes first, and the players take turns. Each move is described by the following sequence of actions: $ \bullet $ If the size of the array is $ 1 $ , the game ends. $ \bullet $ The player who is currently playing chooses two different indices $ i $ , $ j $ ( $ 1 \le i, j \le |a| $ ), and performs the following operation — removes $ a_i $ and $ a_j $ from the array and adds to the array a number equal to $ \lfloor \frac{a_i + a_j}{2} \rfloor \cdot 2 $ . In other words, first divides the sum of the numbers $ a_i $ , $ a_j $ by $ 2 $ rounding down, and then multiplies the result by $ 2 $ . Masha aims to maximize the final number, while Olya aims to minimize it. Masha and Olya decided to play on each non-empty prefix of the initial array $ a $ , and asked for your help. For each $ k = 1, 2, \ldots, n $ , answer the following question. Let only the first $ k $ elements of the array $ a $ be present in the game, with indices $ 1, 2, \ldots, k $ respectively. What number will remain at the end with optimal play by both players?

The first line contains an integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the size of the array. The second line contains $ n $ integers $ a_1,a_2, \ldots,a_n $ ( $ 1 \leq a_i \leq 10^9 $ ) — the array on which Masha and Olya play. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

For each test case, output $ n $ integers. The $ k $ -th of these numbers should be equal to the number that will remain at the end with optimal play by both players, on the array consisting of the first $ k $ elements of the array $ a $ .

In the third test case, for a prefix of length $ 1 $ , the answer is $ 3 $ . For a prefix of length $ 2 $ , Masha has only one move, so the answer is $ 12 $ . For a prefix of length $ 3 $ , Masha has three possible moves: she chooses $ 3 $ and $ 10 $ , then the final number is $ 22 $ , $ 3 $ and $ 11 $ , then the final number is $ 24 $ , $ 10 $ and $ 11 $ , then the final number is $ 22 $ , so Masha will choose $ 3 $ and $ 11 $ and get $ 24 $ .