Read problems statements in Russian here 
The Head Chef is studying the motivation and satisfaction level of his chefs . The motivation and satisfaction of a Chef can be represented as an integer . The Head Chef wants to know the  N  th smallest sum of one satisfaction value and one motivation value for various values of  N  . The satisfaction and motivation values may correspond to the same chef or different chefs . Given two arrays, the first array denoting the motivation value and the second array denoting the satisfaction value of the chefs . We can get a set of sums(add one element from the first array and one from the second). For each query ( denoted by an integer q_{i} ( i = 1 to Q ) , Q denotes number of queries ) , find the q_{i} th element in the set of sums ( in non-decreasing order ) .

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a two space seperated integers K and   Q  denoting the number of chefs and the number of queries . 
The second line of each test case contains K space-separated integers A_{1}, A_{2}, ..., A_{K} denoting the motivation of Chefs. 
The third line of each test case contains K space-separated integers B_{1}, B_{2}, ..., B_{K} denoting the satisfaction of Chefs. 
The next Q lines contain a single integer q_{i} ( for i = 1 to Q ) , find the q_{i} th element in the set of sums .

------ Output ------ 

For each query of each test case, output a single line containing the answer to the query of the testcase 

------ Constraints ------ 

Should contain all the constraints on the input data that you may have. Format it like:

$1 ≤ T ≤ 5$
$1 ≤ K ≤ 20000$
$1 ≤ Q ≤ 500$
$1 ≤ q_{i} ( for i = 1 to Q )  ≤ 10000$
$1 ≤ A_{i} ≤ 10^{18}  ( for i = 1 to K ) $
$1 ≤ B_{i}   ≤ 10^{18} ( for i = 1 to K )  $

------ Example ------ 

Input:
1
3 1
1 2 3
4 5 6
4

Output:
7

------ Explanation ------ 

Example case 1. There are 9 elements in the set of sums : 

1 + 4 = 5 

2 + 4 = 6 

1 + 5 = 6 

1 + 6 = 7 

2 + 5 = 7 

3 + 4 = 7 
 
2 + 6 = 8 

3 + 5 = 8 

3 + 6 = 9 

The fourth smallest element is 7.

Source: codechef | Difficulty: VERY_HARD
Tags: Sorting

Data structures


Solutions:
t = int(input())
for _ in range(t):
	(k, q) = map(int, input().split())
	motivation = sorted(list(map(int, input().split())))
	satisfaction = sorted(list(map(int, input().split())))
	ans = []
	for i in range(min(len(motivation), 10000)):
		for j in range(min(len(satisfaction), 10000 // (i + 1))):
			ans.append(motivation[i] + satisfaction[j])
	ans.sort()
	for _ in range(q):
		query = int(input())
		print(ans[query - 1])


def nSmall():
	l = []
	for i in range(n):
		end = min(n, 10001 // (i + 1))
		for j in range(end):
			l.append(a[i] + b[j])
	return l
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	b = sorted(list(map(int, input().split())))
	arr = sorted(nSmall())
	for _ in range(q):
		print(arr[int(input()) - 1])


for _ in range(int(input())):
	(k, q) = map(int, input().split())
	l = sorted(list(map(int, input().split())))
	l1 = sorted(list(map(int, input().split())))
	a = []
	b = []
	for i in range(k):
		m = min(k, 10001 // (i + 1))
		for j in range(m):
			b.append(l[i] + l1[j])
	b.sort()
	for i in range(q):
		query = int(input())
		print(b[query - 1])


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	b = sorted(list(map(int, input().split())))
	Z = []
	for i in range(n):
		end = min(n, 10001 // (i + 1))
		for j in range(end):
			Z.append(a[i] + b[j])
	Z.sort()
	for i in range(m):
		print(Z[int(input()) - 1])


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	ml = list(map(int, input().split()))
	ml.sort()
	sl = list(map(int, input().split()))
	sl.sort()
	summ = []
	for i in range(n):
		nn = min(n, 10001 // (i + 1))
		for j in range(nn):
			summ.append(sl[i] + ml[j])
	summ.sort()
	for i in range(k):
		q = int(input())
		print(summ[q - 1])


import heapq
for _ in range(int(input().strip())):
	(k, q) = map(int, input().strip().split())
	l1 = list(map(int, input().strip().split()))
	l1.sort()
	l2 = list(map(int, input().strip().split()))
	l2.sort()
	lq = []
	for i in range(q):
		lq.append(int(input().strip()))
	q_max = max(lq)
	ptr = [0] * k
	heap_list = [(l1[i] + l2[0], i) for i in range(k)]
	heapq.heapify(heap_list)
	ans_list = [-1] * (q_max + 1)
	for i in range(1, q_max + 1):
		(su, j) = heapq.heappop(heap_list)
		ans_list[i] = su
		ptr[j] += 1
		if ptr[j] < k:
			heapq.heappush(heap_list, (l1[j] + l2[ptr[j]], j))
	for i in range(q):
		print(ans_list[lq[i]])


from heapq import heapify, heappush, heappop
for _ in range(int(input())):
	(k, Q) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	b = sorted(list(map(int, input().split())))
	s = []
	li = []
	for i in range(k):
		for j in range(min(k, 10000 // (i + 1))):
			s.append(a[i] + b[j])
	heapify(s)
	for i in range(len(s)):
		li.append(heappop(s))
	for i in range(Q):
		q = int(input())
		print(li[q - 1])


from heapq import *
cases = int(input())
for _ in range(cases):
	(k, q) = tuple(map(int, input().split()))
	mot = list(map(int, input().split()))
	sat = list(map(int, input().split()))
	mot.sort()
	sat.sort()
	(ans, heap) = ([], [])
	lim = 10001
	for j in range(k):
		heappush(heap, (mot[0] + sat[j], 0, sat[j]))
	while heap and lim > 0:
		(sm, x, toadd) = heappop(heap)
		ans.append(sm)
		if x + 1 < k:
			heappush(heap, (mot[x + 1] + toadd, x + 1, toadd))
		lim -= 1
	for i in range(q):
		rank = int(input())
		print(ans[rank - 1])


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	f = list(map(int, input().split()))
	f.sort()
	s = list(map(int, input().split()))
	s.sort()
	ans = []
	for i in range(min(n, 10001)):
		minN = min(n, 10001 // (i + 1))
		for j in range(minN):
			ans.append(s[i] + f[j])
	ans.sort()
	for _ in range(k):
		print(ans[int(input()) - 1])


import heapq
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	A = [int(i) for i in input().split()]
	B = [int(i) for i in input().split()]
	A.sort()
	B.sort()
	qry = [int(input()) for i in range(q)]
	leftb = [0] * n
	l = [[A[i] + B[0], i] for i in range(n)]
	heapq.heapify(l)
	m = max(qry)
	ans = [0] * (m + 2)
	z = 0
	for i in range(1, m + 1):
		a = heapq.heappop(l)
		ans[z] = a[0]
		z += 1
		bind = a[1]
		leftb[bind] += 1
		if leftb[bind] != n and bind != n:
			heapq.heappush(l, [A[bind] + B[leftb[bind]], bind])
	for i in qry:
		print(ans[i - 1])


for i in range(int(input())):
	(k, q) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	b = sorted(list(map(int, input().split())))
	sumlist = []
	for j in range(k):
		end = min(k, 10001 // (j + 1))
		for l in range(end):
			sumlist.append(a[j] + b[l])
	sumlist.sort()
	for s in range(q):
		print(sumlist[int(input()) - 1])


from queue import PriorityQueue
for __ in range(int(input())):
	(N, Q) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	A.sort()
	B.sort()
	qarr = []
	for i in range(Q):
		qarr.append(int(input()))
	maxQ = max(qarr)
	pq = PriorityQueue()
	for i in range(N):
		pq.put((A[i] + B[0], i, 0))
	ans = [0] * (maxQ + 1)
	for i in range(1, maxQ + 1):
		temp = pq.get()
		ans[i] = temp[0]
		if temp[2] + 1 < N:
			pq.put((A[temp[1]] + B[temp[2] + 1], temp[1], temp[2] + 1))
	for i in range(Q):
		print(ans[qarr[i]])


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	A = sorted(list(map(int, input().split())))
	B = sorted(list(map(int, input().split())))
	ls = list()
	for i in range(n):
		end = min(n, 10001 // (i + 1))
		for j in range(end):
			ls.append(A[i] + B[j])
	ls.sort()
	for i in range(m):
		print(ls[int(input()) - 1])


x = int(input())
for i in range(x):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	s = list(map(int, input().split()))
	s.sort()
	ans = []
	for i in range(min(n, 10001)):
		m = min(n, 10001 // (i + 1))
		for j in range(m):
			ans.append(s[i] + a[j])
	ans.sort()
	for i in range(k):
		print(ans[int(input()) - 1])


for _ in range(int(input())):
	(k, Q) = map(int, input().split())
	lis1 = list(map(int, input().split()))
	lis2 = list(map(int, input().split()))
	lis1.sort()
	lis2.sort()
	lis = []
	for i in range(min(k, 10001)):
		nn = min(k, 10001 // (i + 1))
		for j in range(nn):
			lis.append(lis1[i] + lis2[j])
	lis.sort()
	while Q > 0:
		pos = int(input())
		print(lis[pos - 1])
		Q -= 1


for t in range(int(input())):
	(k, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	brr = list(map(int, input().split()))
	arr.sort()
	brr.sort()
	qrr = []
	for i in range(q):
		qrr.append(int(input()))
	sums = []
	for i in range(min(k, 10001)):
		for j in range(min(k, 10001 // (i + 1))):
			sums.append(arr[i] + brr[j])
	sums.sort()
	for i in qrr:
		print(sums[i - 1])


t = int(input())
for i in range(0, t):
	(K, Q) = [int(x) for x in input().split()]
	l1 = sorted(list(map(int, input().split())))
	l2 = sorted(list(map(int, input().split())))
	sum = []
	for i in range(K):
		end = min(K, 10001 // (i + 1))
		for j in range(end):
			sum.append(l1[i] + l2[j])
	sum.sort()
	for i in range(Q):
		print(sum[int(input()) - 1])


from heapq import heapify as heap, heappush as push, heappop as pop

def pre_compute(k, mov, sat):
	result = []
	arr = []
	mov.sort()
	sat.sort()
	for i in range(k):
		end = min(k, 10001 // (i + 1))
		for j in range(end):
			push(arr, mov[i] + sat[j])
	c = 10000
	while bool(arr) and c != 0:
		result.append(pop(arr))
		c -= 1
	return result
t = int(input())
for _ in range(t):
	(k, q) = list(map(int, input().split()))
	mov = list(map(int, input().split()))
	sat = list(map(int, input().split()))
	arr = pre_compute(k, mov, sat)
	for _ in range(q):
		ith = int(input())
		print(arr[ith - 1])


from heapq import heapify as heap, heappush as push, heappop as pop

def pre_compute(k, mov, sat):
	arr = []
	mov.sort()
	sat.sort()
	for i in range(k):
		end = min(k, 10001 // (i + 1))
		for j in range(end):
			arr.append(mov[i] + sat[j])
	arr.sort()
	return arr
t = int(input())
for _ in range(t):
	(k, q) = list(map(int, input().split()))
	mov = list(map(int, input().split()))
	sat = list(map(int, input().split()))
	arr = pre_compute(k, mov, sat)
	for _ in range(q):
		ith = int(input())
		print(arr[ith - 1])


t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	m = list(map(int, input().split()))
	m.sort()
	s = list(map(int, input().split()))
	s.sort()
	d = []
	for i in range(n):
		b = min(n, 10001 // (i + 1))
		for j in range(b):
			d.append(m[i] + s[j])
	d.sort()
	for i in range(q):
		c = int(input())
		print(d[c - 1])


for t in range(int(input())):
	(n, q) = list(map(int, input().split()))
	l1 = sorted(list(map(int, input().split())))
	l2 = sorted(list(map(int, input().split())))
	l3 = []
	for i in range(n):
		end = min(n, 10001 // (i + 1))
		for j in range(end):
			l3.append(l1[i] + l2[j])
	l3.sort()
	for i in range(q):
		print(l3[int(input()) - 1])


import heapq

def get_ind(c, n):
	lo = 0
	hi = len(c) - 1
	while lo < hi:
		mid = (lo + hi) // 2
		if c[mid] >= n:
			hi = mid
		else:
			lo = mid + 1
	return lo
for z in range(int(input())):
	(k, qu) = tuple(map(int, input().split()))
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	c = [0 for i in range(k)]
	candi = [(a[i] + b[c[i]], i) for i in range(k)]
	heapq.heapify(candi)
	min_ar = []
	for i in range(min(10000, k * k)):
		ans = heapq.heappop(candi)
		min_ar.append(ans[0])
		if c[ans[1]] < k - 1:
			c[ans[1]] += 1
			heapq.heappush(candi, (a[ans[1]] + b[c[ans[1]]], ans[1]))
	for p in range(qu):
		n = int(input())
		print(min_ar[n - 1])


import heapq
raw_input = input
for _ in range(int(raw_input())):
	(k, q) = map(int, raw_input().split())
	A = sorted([int(x) for x in raw_input().split()])
	B = sorted([int(x) for x in raw_input().split()])
	query = [int(raw_input()) for i in range(q)]
	maxi = max(query)
	left = [0] * k
	L = [(A[i] + B[0], i) for i in range(k)]
	heapq.heapify(L)
	ans = [None] * (maxi + 1)
	for i in range(1, maxi + 1):
		(temp, idx) = heapq.heappop(L)
		ans[i] = temp
		left[idx] += 1
		if left[idx] < k:
			heapq.heappush(L, (A[idx] + B[left[idx]], idx))
	for i in query:
		print(ans[i])


for _ in range(int(input())):
	(k, q) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	arr = []
	for i in range(min(10001, k)):
		nn = min(k, 10001 // (i + 1))
		for j in range(min(10001, nn)):
			arr.append(a[i] + b[j])
	arr.sort()
	for k in range(q):
		query = int(input())
		print(arr[query - 1])


class BinHeap:

	def __init__(self):
		self.heaplist = [0]
		self.currentSize = 0

	def percUp(self, i):
		while i // 2 > 0:
			if self.heaplist[i][0] < self.heaplist[i // 2][0]:
				tmp = self.heaplist[i // 2]
				self.heaplist[i // 2] = self.heaplist[i]
				self.heaplist[i] = tmp
			i = i // 2

	def insert(self, k):
		self.heaplist.append(k)
		self.currentSize = self.currentSize + 1
		self.percUp(self.currentSize)

	def percDown(self, i):
		while i * 2 <= self.currentSize:
			mc = self.minChild(i)
			if self.heaplist[i][0] > self.heaplist[mc][0]:
				tmp = self.heaplist[i]
				self.heaplist[i] = self.heaplist[mc]
				self.heaplist[mc] = tmp
			i = mc

	def minChild(self, i):
		if i * 2 + 1 > self.currentSize:
			return i * 2
		elif self.heaplist[i * 2][0] < self.heaplist[i * 2 + 1][0]:
			return i * 2
		else:
			return i * 2 + 1

	def delMin(self):
		retval = self.heaplist[1]
		self.heaplist[1] = self.heaplist[self.currentSize]
		self.currentSize = self.currentSize - 1
		self.heaplist.pop()
		self.percDown(1)
		return retval

	def buildHeap(self, alist):
		i = len(alist) // 2
		self.currentSize = len(alist)
		self.heaplist = [0] + alist[:]
		while i > 0:
			self.percDown(i)
			i = i - 1
for _ in range(int(input().strip())):
	(k, q) = map(int, input().strip().split())
	a = list(map(int, input().strip().split()))
	a.sort()
	b = list(map(int, input().strip().split()))
	b.sort()
	queries = [int(input().strip()) for i in range(q)]
	max_query = max(queries)
	ptr = [0 for i in range(k)]
	list_of_sums = [(a[i] + b[ptr[i]], i) for i in range(k)]
	bh = BinHeap()
	bh.buildHeap(list_of_sums)
	answer = [-1 for i in range(max_query + 1)]
	for i in range(1, max_query + 1):
		(ans, idx) = bh.delMin()
		ptr[idx] += 1
		answer[i] = ans
		if ptr[idx] < k:
			bh.insert((a[idx] + b[ptr[idx]], idx))
	for query in queries:
		print(answer[query])


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	l1 = sorted(list(map(int, input().split())))
	l2 = sorted(list(map(int, input().split())))
	l = []
	for i in range(min(n, 1001)):
		for j in range(min(n, 1001)):
			l.append(l1[i] + l2[j])
	l.sort()
	for i in range(q):
		k = int(input())
		print(l[k - 1])


try:
	for _ in range(int(input())):
		(K, Q) = map(int, input().split())
		m = list(map(int, input().split()))
		s = list(map(int, input().split()))
		m.sort()
		s.sort()
		Q_list = []
		memory = []
		total = 0
		for __ in range(Q):
			Q_list.append(int(input()))
		for l in range(1, len(s) + 1):
			for j in range(min(len(s), 10001 // l)):
				memory.append(m[l - 1] + s[j])
		memory.sort()
		for i in range(len(Q_list)):
			print(memory[Q_list[i] - 1])
except:
	pass


def in1():
	return int(input())
for _ in range(in1()):
	(k, q) = map(int, input().split())
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	arr1.sort()
	arr2.sort()
	ans = []
	for i in range(min(k, 10001)):
		nn = min(k, 10001 // (i + 1))
		for j in range(nn):
			ans.append(arr1[i] + arr2[j])
	ans.sort()
	for qu in range(q):
		query = int(input())
		print(ans[query - 1])


for _ in range(int(input())):
	(k, q) = map(int, input().split())
	l1 = sorted(list(map(int, input().split())))
	l2 = sorted(list(map(int, input().split())))
	s = []
	for i in range(k):
		nn = min(k, 10001 // (i + 1))
		for j in range(nn):
			s.append(l1[i] + l2[j])
	s.sort()
	for x in range(q):
		i = int(input())
		print(s[i - 1])


from sys import stdin
input = stdin.readline
import heapq

def answer():
	ans = []
	for i in range(n):
		for j in range(min(n, 10000 // (i + 1))):
			ans.append(a[i] + b[j])
	ans.sort()
	for x in range(q):
		ind = int(input())
		print(ans[ind - 1])
for T in range(int(input())):
	(n, q) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	b = sorted(list(map(int, input().split())))
	answer()