#581 Rating Updates

Loading problem...

Preparing the statement, recent submissions, and submit form.

#581 Rating Updates

Time limit: 1000 ms
Memory limit: 1024 MB
Checker: TOKEN
Solve threshold: 100

Statement

Statement language

The initial rating is $R_0$ . You participate in $N$ contests in order, and your performance in the $i$ -th contest is $P_i$ .

After each contest, the rating is updated by giving weight $3$ to the previous rating and weight $1$ to the current performance. The rating $R_i$ after the $i$ -th contest is

R_i=\frac{3R_{i-1}+P_i}{4}.

It is guaranteed that $R_i$ is a positive integer for every $i$ ( $1\leq i\leq N$ ).

Find the final rating $R_N$ .

Input

The input is given in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$N\ R_0$ $P_1\ P_2\ \cdots\ P_N$

$T$ is the number of test cases. Each case gives the initial rating $R_0$ , the number of contests $N$ , and the $N$ performances $P_1,P_2,\cdots,P_N$ in contest order.

Output

For each test case, print the final rating $R_N$ on one line.

Constraints

$1 \leq T \leq 100\,000$ .
$1 \leq N \leq 200\,000$ .
$1 \leq R_0 \leq 5\cdot10^8$ .
$1 \leq P_i \leq 5\cdot10^8$ ( $1 \leq i \leq N$ ).
The rating $R_i$ after every contest is an integer satisfying $1 \leq R_i \leq 5\cdot10^8$ ( $1 \leq i \leq N$ ).
The sum of $N$ over all test cases is at most $200\,000$ .

Subtasks

#	Score	Constraints
1	37	$P_i\geq R_{i-1}$ ( $1\leq i\leq N$ ).
2	63	No additional constraints.

Samples

Sample 1

Input

Output

110
2
4

In the first case, the rating changes as $100 \longrightarrow 105 \longrightarrow 100 \longrightarrow 110$ .

Sample 2

Input

2
2 500000000
500000000 500000000
2 100
60 54

Output

500000000
81

In the first case, each performance equals the current rating, so the rating stays unchanged. In the second case, it changes as $100 \longrightarrow90 \longrightarrow81$ .

Editorial

View editorial