Timur has a stairway with $n$ steps. The $i$-th step is $a_i$ meters higher than its predecessor. The first step is $a_1$ meters higher than the ground, and the ground starts at $0$ meters.

The stairs for the first test case.

Timur has $q$ questions, each denoted by an integer $k_1, \dots, k_q$. For each question $k_i$, you have to print the maximum possible height Timur can achieve by climbing the steps if his legs are of length $k_i$. Timur can only climb the $j$-th step if his legs are of length at least $a_j$. In other words, $k_i \geq a_j$ for each step $j$ climbed.

Note that you should answer each question independently.


-----Input-----

The first line contains a single integer $t$ ($1 \leq t \leq 100$) — the number of test cases.

The first line of each test case contains two integers $n, q$ ($1 \leq n, q \leq 2\cdot10^5$) — the number of steps and the number of questions, respectively.

The second line of each test case contains $n$ integers ($1 \leq a_i \leq 10^9$) — the height of the steps.

The third line of each test case contains $q$ integers ($0 \leq k_i \leq 10^9$) — the numbers for each question.

It is guaranteed that the sum of $n$ does not exceed $2\cdot10^5$, and the sum of $q$ does not exceed $2\cdot10^5$.


-----Output-----

For each test case, output a single line containing $q$ integers, the answer for each question.

Please note, that the answer for some questions won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).


-----Examples-----

Input
3
4 5
1 2 1 5
1 2 4 9 10
2 2
1 1
0 1
3 1
1000000000 1000000000 1000000000
1000000000
Output
1 4 4 9 9 
0 2 
3000000000


-----Note-----

Consider the first test case, pictured in the statement.

If Timur's legs have length $1$, then he can only climb stair $1$, so the highest he can reach is $1$ meter.

If Timur's legs have length $2$ or $4$, then he can only climb stairs $1$, $2$, and $3$, so the highest he can reach is $1+2+1=4$ meters.

If Timur's legs have length $9$ or $10$, then he can climb the whole staircase, so the highest he can reach is $1+2+1+5=9$ meters.

In the first question of the second test case, Timur has no legs, so he cannot go up even a single step. :(

Difficulty: EASY
Tags: Sorting

Mathematics

Greedy algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	A = list(map(int, input().split()))
	Q = list(map(int, input().split()))
	sortQ = sorted(Q)
	height = 0
	i = 0
	dico = {}
	for k in sortQ:
		while i < n and A[i] <= k:
			height += A[i]
			i += 1
		dico[k] = height
	print(' '.join([str(dico[p]) for p in Q]))


import bisect

def solve(s, q):
	ms = []
	mh = 0
	cnt = 0
	ss = []
	res = []
	for e in s:
		cnt += e
		mh = max(mh, e)
		ms.append(mh)
		ss.append(cnt)
	for k in q:
		idx = bisect.bisect(ms, k)
		res.append(ss[idx - 1] if idx != 0 else 0)
	return ' '.join([str(e) for e in res])

def main():
	for _ in range(int(input())):
		_ = input()
		s = [int(e) for e in input().split()]
		q = [int(e) for e in input().split()]
		print(solve(s, q))
main()


def solve():
	t = int(input())
	for _ in range(t):
		(n, q) = map(int, input().split())
		steps = list(map(int, input().split()))
		questions = list(map(int, input().split()))
		answers = [0] * len(questions)
		indexes = sorted(enumerate(questions), key=lambda q: q[1])
		height = 0
		index = 0
		for step in steps:
			while index < len(indexes) and indexes[index][1] < step:
				answers[indexes[index][0]] = height
				index += 1
			height += step
		while index < len(indexes):
			answers[indexes[index][0]] = height
			index += 1
		print(' '.join(map(str, answers)))
solve()


import bisect
ts = int(input())
for i in range(ts):
	(n, x) = [int(i) for i in input().split()]
	ar = [int(i) for i in input().split()]
	(a, b) = ([], [0])
	(c, s) = (0, 0)
	for i in ar:
		c = max(i, c)
		s += i
		a.append(c)
		b.append(s)
	y = [int(i) for i in input().split()]
	res = []
	for i in y:
		ind = bisect.bisect(a, i)
		res.append(b[ind])
	print(' '.join(map(str, res)))


import bisect

def get_max_heights(a, k):
	prefix_max = a.copy()
	prefix_sum = a.copy()
	for i in range(1, len(a)):
		prefix_max[i] = max(prefix_max[i], prefix_max[i - 1])
		prefix_sum[i] += prefix_sum[i - 1]
	max_heights = []
	for k_i in k:
		max_height_idx = bisect.bisect_right(prefix_max, k_i) - 1
		if max_height_idx < 0:
			max_heights.append('0')
			continue
		max_height = prefix_sum[max_height_idx]
		max_heights.append(str(max_height))
	return max_heights

def main():
	t = int(input())
	for _ in range(t):
		(n, q) = map(int, input().split())
		a = list(map(int, input().split()))
		k = list(map(int, input().split()))
		max_heights = get_max_heights(a, k)
		print(' '.join(max_heights))
main()


import os
import math
import collections
import bisect
import functools
import itertools
import heapq

def solve(a, queries):
	n = len(a)
	m = a[:]
	for i in range(1, n):
		m[i] = max(m[i], m[i - 1])
	pre = [0] * (n + 1)
	for i in range(n):
		pre[i + 1] = pre[i] + a[i]
	ans = []
	for x in queries:
		i = bisect.bisect_left(m, x + 1) - 1
		ans.append(pre[i + 1])
	return ans
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	queries = list(map(int, input().split()))
	print(' '.join((str(x) for x in solve(a, queries))))


from bisect import bisect
for tcase in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	k = list(map(int, input().split()))
	(s, m) = ([0], [0])
	for ai in a:
		s.append(s[-1] + ai)
		m.append(max(m[-1], ai))
	ans = []
	for ki in k:
		i = bisect(m, ki)
		ans.append(s[i - 1])
	print(' '.join(map(str, ans)))


import bisect
t = int(input())
while t > 0:
	t -= 1
	(n, q) = map(int, input().split())
	arrN = list(map(int, input().split()))
	arrQ = list(map(int, input().split()))
	arrSave = []
	arrMax = []
	j = 1
	for (i, x) in enumerate(arrN):
		if i == 0:
			arrSave.append(x)
			arrMax.append(x)
		else:
			arrSave.append(arrSave[i - 1] + x)
			arrMax.append(max(arrMax[i - 1], x))
	resultArray = []
	for x in arrQ:
		indexResult = bisect.bisect(arrMax, x) - 1
		if indexResult < 0:
			resultArray.append(str(0))
		else:
			resultArray.append(str(arrSave[indexResult]))
	print(' '.join(resultArray))


from bisect import *
Rsydgcfhb_ydga = lambda : map(int, input().split())
(t,) = Rsydgcfhb_ydga()
while t:
	t -= 1
	Rsydgcfhb_ydga()
	a = [0]
	b = [0]
	for x in Rsydgcfhb_ydga():
		a += (max(a[-1], x),)
		b += (b[-1] + x,)
	print(*(b[bisect(a, y) - 1] for y in Rsydgcfhb_ydga()))


import bisect

def main():
	(n, q) = map(int, input().split())
	heights_arr = list(map(int, input().split()))
	questions_arr = list(map(int, input().split()))
	prev = heights_arr[0]
	my_max_till_i = prev
	my_max_arr = [0 for i in range(n)]
	sum_till_i = [0] + [heights_arr[0] for i in range(n)]
	for index in range(0, n):
		my_max_till_i = max(heights_arr[index], my_max_till_i)
		my_max_arr[index] = my_max_till_i
		if not index:
			continue
		sum_till_i[index + 1] = sum_till_i[index] + heights_arr[index]
	result = [0 for i in range(len(questions_arr))]
	for (index, step_size) in enumerate(questions_arr):
		ans_idx = bisect.bisect_right(my_max_arr, step_size)
		result[index] = sum_till_i[ans_idx]
	print(*result, sep=' ')
t = int(input())
for _ in range(t):
	main()


def solve():
	(n, k) = map(int, input().split())
	lis = list(map(int, input().split()))
	k = list(map(int, input().split()))
	pref = [0] * n
	s = 0
	for i in range(n):
		s += lis[i]
		pref[i] = s
	from bisect import bisect_right
	Mx = lis[0]
	for i in range(1, n):
		Mx = max(Mx, lis[i])
		lis[i] = Mx
	ans = list()
	for i in k:
		ind = bisect_right(lis, i)
		if ind == 0:
			ans.append(0)
		else:
			ans.append(pref[ind - 1])
	print(*ans)
for _ in range(int(input())):
	solve()


from bisect import bisect
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	N = list(map(int, input().split()))
	Q = list(map(int, input().split()))
	hiarr = [0] * n
	csum = [0] * n
	lasthi = -1
	csum[0] = N[0]
	hiarr[0] = N[0]
	for i in range(1, n):
		csum[i] += csum[i - 1] + N[i]
		hiarr[i] = max(hiarr[i - 1], N[i])
	res = [0] * q
	for i in range(q):
		ind = bisect(hiarr, Q[i]) - 1
		if ind < 0:
			res[i] = 0
		else:
			res[i] = csum[ind]
	print(' '.join(map(str, res)))


from collections import defaultdict, deque, Counter
from functools import lru_cache
from heapq import heappush, heappop
from bisect import bisect_right, bisect_left

def inpNum():
	return int(input())

def inpStr():
	return input()

def inpSepNum():
	return map(int, input().split())

def inpNumList():
	return list(map(int, input().split()))

def inpChList():
	return list(input().split())
tc = inpNum()
for _ in range(tc):
	(n, q) = inpSepNum()
	stairs = inpNumList()
	prefix = [0]
	ques = inpNumList()
	cur = stairs[0]
	for i in range(n):
		prefix.append(prefix[-1] + stairs[i])
		if stairs[i] < cur:
			stairs[i] = cur
		else:
			cur = stairs[i]
	ans = []
	for q in ques:
		pos = bisect_right(stairs, q)
		ans.append(prefix[pos])
	print(*ans)


t = int(input())
from bisect import bisect_right
for ncase in range(1, t + 1):
	(n, q) = [int(s) for s in input().split(' ')]
	nn = [int(s) for s in input().split(' ')]
	qq = [int(s) for s in input().split(' ')]
	d = {0: 0, nn[0]: nn[0]}
	dmax = nn[0]
	for i in range(1, n):
		if nn[i] > dmax:
			d[nn[i]] = d[dmax] + nn[i]
			dmax = nn[i]
		else:
			d[dmax] += nn[i]
	key = sorted(d.keys())
	ans = []
	for i in range(q):
		k = bisect_right(key, qq[i])
		ans.append(str(d[key[k - 1]]))
	print(' '.join(ans))


from bisect import bisect_right
from itertools import accumulate

def solution():
	(n, q) = map(int, input().split())
	a = [int(num) for num in input().split()]
	k = [int(num) for num in input().split()]
	ans = []
	acc = list(accumulate(a, initial=0))
	b = []
	maximum = -float('Inf')
	for num in a:
		maximum = max(maximum, num)
		b.append(maximum)
	for j in range(q):
		index = bisect_right(b, k[j])
		if index == len(b):
			ans.append(acc[-1])
		else:
			ans.append(acc[index])
	print(*ans)

def main():
	t = int(input())
	while t:
		solution()
		t -= 1
main()


import bisect
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	k = list(map(int, input().split()))
	p = [0]
	for i in a:
		p.append(p[-1] + i)
	m = [a[0]]
	for i in a[1:]:
		m.append(max(m[-1], i))
	print(*[p[bisect.bisect_right(m, i)] for i in k])


from bisect import bisect
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	k = list(map(int, input().split()))
	k_sorted = k[:]
	k_sorted.sort()
	ans = {}
	h = i = 0
	for ki in k_sorted:
		while i < n and a[i] <= ki:
			h += a[i]
			i += 1
		ans[ki] = h
	for i in k:
		print(ans[i], end=' ')
	print()