Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Consider $N$ binary variables $x_{1}, x_{2}, \ldots, x_{N}$. For each valid $i$, the $i$-th of these variables can be $x_{i} = 0$ or $x_{i} = 1$; therefore, there are $2^{N}$ possible assignments of values to the variables. For each valid $i$, setting $x_{i} = 1$ gives you score $g_{i}$.

In addition, there are $M$ special intervals (numbered $1$ through $M$). For each valid $i$, the $i$-th interval is $[u_{i}, v_{i}]$ and if $x_{u_{i}} = x_{u_{i}+1} = \ldots = x_{v_{i}} = 1$, then your score increases by $d_{i}$.

Note that both $g_{i}$ and $d_{i}$ can be negative (setting more variables to $1$ can decrease your score), and your score can also be negative. Formally, the score of an assignment of values to the binary variables is
$$\sum_{i=1}^N g_{i} \cdot x_{i} + \sum_{i=1}^M d_{i} \cdot \prod_{j=u_{i}}^{v_{i}} x_{j} \,.$$

Find the $K$ highest scores among all assignments on these variables. Formally, if we computed the scores of all $2^{N}$ assignments and sorted them in non-increasing order, you should find the first $K$ of these values.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains three space-separated integers $N$, $M$ and $K$.
The second line contains $N$ space-separated integers $g_{1}, g_{2}, \ldots, g_{N}$.
$M$ lines follow. For each valid $i$, the $i$-th of these lines contains three space-separated integers $u_{i}$, $v_{i}$ and $d_{i}$.

------  Output ------
For each test case, print a single line containing $K$ space-separated integers ― the $K$ highest scores of assignments on the binary variables, in decreasing order.

------  Constraints ------
$1 ≤ T ≤ 10$
$1 ≤ N ≤ 60$
$1 ≤ M ≤ \min(N \cdot (N-1) / 2, 1,000)$
$1 ≤ K ≤ \min(2^{N}, 200)$
$|g_{i}| ≤ 10^{9}$ for each valid $i$
$1 ≤ u_{i} < v_{i} ≤ N$ for each valid $i$
for each valid $i$ and $j$ ($i \neq j$), $u_{i} \neq u_{j}$ or $v_{i} \neq v_{j}$
$|d_{i}| ≤ 10^{9}$ for each valid $i$
the sum of $N$ over all test cases does not exceed $60$

------  Subtasks ------
Subtask #1 (5 points): the sum of $N$ over all test cases does not exceed $18$

Subtask #2 (20 points): $K = 1$

Subtask #3 (75 points): original constraints

----- Sample Input 1 ------ 
1

4 2 3

-4 -2 5 2

1 3 0

1 4 -3
----- Sample Output 1 ------ 
7 5 5
----- explanation 1 ------ 
Example case 1: The best assignment is $x = (0,0,1,1)$, with score $7$. The second and third best assignments are $(0,0,1,0)$ and $(0,1,1,1)$, each with score $5$.

Difficulty: HARD
Tags: Dynamic programming

Complete search
Skill types: Dynamic programming

Complete search

Starter code:

Solutions:
from sys import stdin
input = stdin.readline

def answer():
	dp = [[] for i in range(n + 1)]
	dp[0].append(0)
	for i in range(1, n + 1):
		dp[i].extend(dp[i - 1])
		for j in range(i, 0, -1):
			x = 0
			for l in range(j, i + 1):
				for r in range(l, i + 1):
					x += value[l][r]
			if j == 1:
				dp[i].append(x)
			else:
				for val in dp[j - 2]:
					dp[i].append(val + x)
		dp[i].sort(reverse=True)
		while len(dp[i]) > k:
			dp[i].pop()
	return dp[n]
for T in range(int(input())):
	(n, m, k) = map(int, input().split())
	g = list(map(int, input().split()))
	value = [[0 for i in range(n + 1)] for j in range(n + 1)]
	for i in range(m):
		(x, y, val) = map(int, input().split())
		value[x][y] = val
	for i in range(n):
		value[i + 1][i + 1] = g[i]
	print(*answer())


for T in range(int(input())):
	(n, m, k) = map(int, input().split())
	g = list(map(int, input().split()))
	value = [[0 for i in range(n + 1)] for j in range(n + 1)]
	for i in range(m):
		(x, y, val) = map(int, input().split())
		value[x][y] = val
	for i in range(n):
		value[i + 1][i + 1] = g[i]
	dp = [[] for i in range(n + 1)]
	dp[0].append(0)
	for i in range(1, n + 1):
		dp[i].extend(dp[i - 1])
		for j in range(i, 0, -1):
			x = 0
			for l in range(j, i + 1):
				for r in range(l, i + 1):
					x += value[l][r]
			if j == 1:
				dp[i].append(x)
			else:
				for val in dp[j - 2]:
					dp[i].append(val + x)
		dp[i].sort(reverse=True)
		while len(dp[i]) > k:
			dp[i].pop()
	print(*dp[n])


for test in range(int(input())):
	(n, m, k1) = map(int, input().split())
	g = [0]
	gt = list(map(int, input().split()))
	g.extend(gt)
	pos = [[] for x in range(n + 1)]
	for i in range(m):
		(u, v, d) = map(int, input().split())
		pos[u].append([i, d])
		pos[v].append([i, d])
	dp = [[] for x in range(n + 1)]
	dp[0].append([0, 0])
	for i in range(1, n + 1):
		temp = []
		temp.extend(dp[i - 1])
		cur = 0
		mask = 0
		open1 = {}
		for j in range(i, 0, -1):
			cur += g[j]
			mask = mask ^ 1 << j
			for k in pos[j]:
				if k[0] in open1:
					cur += k[1]
				else:
					open1[k[0]] = 1
			if j > 1:
				for k in dp[j - 2]:
					temp.append([k[0] + cur, mask ^ k[1]])
			else:
				temp.append([cur, mask])
		temp.sort()
		temp = temp[::-1]
		sel = {}
		filled = 0
		j = 0
		while j < len(temp) and filled < k1:
			if temp[j][1] in sel:
				j += 1
			else:
				dp[i].append(temp[j])
				filled += 1
				sel[temp[j][1]] = 1
				j += 1
	dp[n].sort(reverse=True)
	for i in range(k1):
		print(dp[n][i][0], end=' ')
	print()


def solve():
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	av = [[] for j in range(n + 1)]
	res = [[] for j in range(n + 1)]
	for i in range(m):
		(u, v, d) = map(int, input().split())
		av[u].append((i, d))
		av[v].append((i, d))
	res[0].append((0, 0))
	for i in range(1, n + 1):
		temp = []
		temp += res[i - 1]
		cur = 0
		mask = 0
		o = []
		for j in reversed(range(1, i + 1)):
			cur += a[j - 1]
			mask ^= 1 << j
			for x in av[j]:
				if x[0] in o:
					cur += x[1]
				else:
					o.append(x[0])
			if j > 1:
				for x in res[j - 2]:
					temp.append((x[0] + cur, mask ^ x[1]))
			else:
				temp.append((cur, mask))
		temp = sorted(temp, key=lambda x: (x[0], x[1]), reverse=True)
		selected = []
		fill = 0
		for j in range(len(temp)):
			if k <= fill:
				break
			if temp[j][1] in selected:
				print('yes')
				continue
			res[i].append(temp[j])
			fill += 1
			selected.append(temp[j][1])
	return ''.join((str(res[n][i][0]) + ' ' for i in range(k)))
for z in range(int(input())):
	print(solve())


import functools

def compare(i, j):
	if i[0] > j[0]:
		return -1
	elif i[0] < j[0]:
		return 1
	elif i[1] > j[1]:
		return -1
	elif i[1] < j[1]:
		return 1
	else:
		return 0
t = int(input())
for _ in range(t):
	(n, m, k) = list(map(int, input().strip().split()))
	g = list(map(int, input().strip().split()))
	g.insert(0, 0)
	arr = [[] for i in range(n + 1)]
	dp = [[] for i in range(n + 1)]
	for i in range(m):
		(u, v, d) = list(map(int, input().strip().split()))
		arr[u].append([i, d])
		arr[v].append([i, d])
	dp[0].append([0, 0])
	for i in range(1, n + 1):
		yo = []
		for aa in dp[i - 1]:
			yo.append(aa)
		cu = 0
		ma = 0
		o = set()
		for j in range(i, 0, -1):
			cu += g[j]
			ma = ma ^ 1 << j
			for p in arr[j]:
				if p[0] in o:
					cu += p[1]
				else:
					o.add(p[0])
			if j > 1:
				for p in dp[j - 2]:
					yo.append([p[0] + cu, ma ^ p[1]])
			else:
				yo.append([cu, ma])
		yo.sort(key=functools.cmp_to_key(compare))
		sel = set()
		f = 0
		for j in range(len(yo)):
			if f >= k:
				break
			if yo[j][1] in sel:
				continue
			dp[i].append(yo[j])
			f += 1
			sel.add(yo[j][1])
	for i in range(k):
		print(dp[n][i][0], end=' ')
	print()


def build_temp_cache(G, ind, Dscore, cache, prev_cache, curr_ind):
	temp_cache = []
	for cache_element in cache:
		temp_cache.append(cache_element)
	simple_score = 0
	mp = {}
	two_pw = 0
	for j in range(curr_ind, 0, -1):
		simple_score += G[j]
		two_pw = two_pw ^ 2 ** j
		for l in range(len(Dscore[j])):
			if ind[j][l] in mp:
				simple_score += Dscore[j][l]
			else:
				mp[ind[j][l]] = 1
		if j > 1:
			for cache_element in prev_cache[j - 2]:
				temp_cache.append((cache_element[0] + simple_score, two_pw ^ cache_element[1]))
		else:
			temp_cache.append((simple_score, two_pw))
	return temp_cache

def build_cache(temp_cache, k):
	mp = {}
	cnt = 0
	j = 0
	cache = []
	temp_cache.sort()
	temp_cache.reverse()
	while j < len(temp_cache) and cnt < k:
		if temp_cache[j][1] not in mp:
			cache.append(temp_cache[j])
			cnt += 1
			mp[temp_cache[j][1]] = 1
		j += 1
	return cache
T = int(input())
for t in range(T):
	(n, m, k) = map(int, input().split())
	G = [0] + list(map(int, input().split()))
	(ind, Dscore) = ([], [])
	for i in range(n + 1):
		ind.append([])
		Dscore.append([])
	for i in range(m):
		(u, v, d) = map(int, input().split())
		Dscore[u].append(d)
		Dscore[v].append(d)
		ind[u].append(i)
		ind[v].append(i)
	cache = [(0, 0)]
	prev_cache = []
	for i in range(1, n + 1):
		temp_cache = build_temp_cache(G, ind, Dscore, cache, prev_cache, i)
		prev_cache.append([])
		for each_c in cache:
			prev_cache[i - 1].append(each_c)
		cache = build_cache(temp_cache, k)
	for i in range(k):
		print(cache[i][0], end=' ')
	print('')


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	g = list(map(int, input().split()))
	g.insert(0, 0)
	lis = []
	dp = []
	for _ in range(n + 1):
		lis.append([])
		dp.append([])
	for i in range(m):
		(u, v, d) = map(int, input().split())
		lis[u].append([i, d])
		lis[v].append([i, d])
	dp[0].append([0, 0])
	for i in range(1, n + 1):
		temp_lis = []
		for j in dp[i - 1]:
			temp_lis.append(j)
		curr = 0
		mask = 0
		s = set()
		for j in range(i, 0, -1):
			curr += g[j]
			mask = mask ^ 1 << j
			for pointer in lis[j]:
				if pointer[0] in s:
					curr += pointer[1]
				else:
					s.add(pointer[0])
			if j > 1:
				for pointer in dp[j - 2]:
					temp_lis.append([pointer[0] + curr, mask ^ pointer[1]])
			else:
				temp_lis.append([curr, mask])
		temp_lis.sort(key=lambda x: x[0])
		temp_lis = temp_lis[::-1]
		sel = set()
		filled = 0
		j = 0
		while j < len(temp_lis) and filled < k:
			if temp_lis[j][1] in sel:
				j += 1
				continue
			dp[i].append(temp_lis[j])
			filled += 1
			sel.add(temp_lis[j][1])
			j += 1
	ans = []
	for i in range(k):
		ans.append(dp[n][i][0])
	print(*ans)


def printAns(k, dp):
	for i in range(k):
		print(dp[n][i][0], end=' ')
	print()

def solve(n, m, k1, l, dp):
	dp[0].append((0, 0))
	for i in range(1, n + 1):
		tmp = []
		for j in dp[i - 1]:
			tmp.append(j)
		cr = 0
		mk = 0
		opn = set()
		for j in range(i, 0, -1):
			cr += g[j]
			mk ^= 1 << j
			for ptr in l[j]:
				if ptr[0] in opn:
					cr += ptr[1]
				else:
					opn.add(ptr[0])
			if j > 1:
				for ptr in dp[j - 2]:
					tmp.append((ptr[0] + cr, mk ^ ptr[1]))
			else:
				tmp.append((cr, mk))
		tmp.sort(key=lambda tmp: tmp[0])
		tmp.reverse()
		slt = set()
		j = 0
		fl = 0
		while j < len(tmp) and fl < k1:
			if tmp[j][1] in slt:
				j += 1
				continue
			dp[i].append(tmp[j])
			fl += 1
			slt.add(tmp[j][1])
	printAns(k1, dp)
for _ in range(int(input())):
	(n, m, k1) = map(int, input().split())
	g = list(map(int, input().split()))
	g.insert(0, 0)
	l = []
	dp = []
	for i in range(n + 1):
		l.append([])
		dp.append([])
	for i in range(m):
		(u, v, d) = map(int, input().split())
		l[u].append((i, d))
		l[v].append((i, d))
	solve(n, m, k1, l, dp)


import sys
import os.path
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
depth = 1000005
mod = 1000000007
sys.setrecursionlimit(depth)
from collections import defaultdict
from math import inf
from heapq import heapify, merge, nlargest
a = b = c = n = m = None

def compute(index, curr):
	r = index
	l = index - curr
	res = a[index]
	for i in range(1, m + 1):
		e = b[i]
		if e[0] >= l and e[1] == r:
			res += e[2]
	return res

def solve(index, curr):
	if index == n:
		return sorted([0, compute(index, curr)])
	if dp[index, curr] != -1:
		return dp[index, curr]
	s1 = solve(index + 1, 0)
	s2 = solve(index + 1, curr + 1)
	val = compute(index, curr)
	s2 = [e + val for e in s2]
	ans = list(merge(s1, s2))
	if len(ans) > k:
		ans = list(nlargest(k, ans))
	dp[index, curr] = ans
	return dp[index, curr]
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = [0] + list(map(int, input().split()))
	b = [0 for _ in range(m + 1)]
	for i in range(1, m + 1):
		(u, v, w) = map(int, input().split())
		b[i] = (u, v, w)
	dp = defaultdict(lambda : -1)
	ans = solve(1, 0)
	ans.sort(reverse=True)
	ans = ans[:k]
	print(*ans)


import io, sys

def inpt():
	return sys.stdin.readline()

def getints():
	return map(int, sys.stdin.readline().split())

def getlist():
	return list(getints())

def prnt(val):
	sys.stdout.write(str(val) + '\n')

def solve():
	(n, m, k) = getints()
	grr = [0] + getlist()
	mr = [getlist() for i in range(m)]
	(mrr, dp) = ({i: [] for i in range(n + 1)}, {i: [] for i in range(n + 1)})
	for i in range(m):
		mrr[mr[i][0]].append([i, mr[i][2]])
		mrr[mr[i][1]].append([i, mr[i][2]])
	dp[0].append([0, 0])
	for i in range(1, n + 1):
		temp = []
		for val in dp[i - 1]:
			temp.append(val)
		(curr, mask) = (0, 0)
		op = set()
		for j in range(i, 0, -1):
			curr += grr[j]
			mask ^= 2 ** j
			for val in mrr[j]:
				if val[0] in op:
					curr += val[1]
				else:
					op.add(val[0])
			if j > 1:
				for valj in dp[j - 2]:
					temp.append([valj[0] + curr, valj[1] ^ mask])
			else:
				temp.append([curr, mask])
		temp.sort(reverse=True)
		(sel, filled) = (set(), 0)
		j = 0
		while j < len(temp) and filled < k:
			if temp[j][1] in sel:
				j += 1
				continue
			dp[i].append(temp[j])
			filled += 1
			sel.add(temp[j][1])
			j += 1
	for val in dp[n]:
		sys.stdout.write(str(val[0]) + ' ')
	sys.stdout.write('\n')
for _ in range(int(inpt())):
	solve()


INF = 1e+18
t = int(input())
for _ in range(t):
	all_ans = []
	(n, m, K) = list(map(int, input().split()))
	g = [0] * (n + 1)
	temp = list(map(int, input().split()))
	for i in range(0, n):
		g[i + 1] = temp[i]
	intervals = []
	arr = [[] for _ in range(n + 1)]
	dp = [[] for _ in range(n + 1)]
	for i in range(m):
		(u, v, d) = list(map(int, input().split()))
		arr[u].append((i, d))
		arr[v].append((i, d))
	dp[0].append((0, 0))
	for i in range(1, n + 1):
		temp = []
		for j in dp[i - 1]:
			temp.append(j)
		open = set()
		curr = 0
		mask = 0
		for k in range(i, 0, -1):
			curr += g[k]
			mask = mask ^ 1 << k
			for xyz in arr[k]:
				if xyz[0] in open:
					curr += xyz[1]
				else:
					open.add(xyz[0])
			if k > 1:
				for xyzj in dp[k - 2]:
					temp.append((xyzj[0] + curr, mask ^ xyzj[1]))
			else:
				temp.append((curr, mask))
		temp.sort()
		temp = temp[::-1]
		sel = set()
		filled = 0
		for j in range(0, len(temp)):
			if filled == K:
				break
			if temp[j][1] in sel:
				continue
			dp[i].append(temp[j])
			filled += 1
			sel.add(temp[j][1])
	ans = []
	for i in range(K):
		ans.append(dp[n][i][0])
	print(*ans)


t = int(input())
tt = 0
for tt in range(0, t):
	ans = 0
	num5 = []
	num = input().split(' ')
	outcome = 0
	n = int(num[0])
	num5.append(n)
	m = int(num[1])
	num5.append(m)
	k = int(num[2])
	num5.append(k)
	g = input().split(' ')
	for find in range(0, len(num5)):
		if num[find] == n:
			ans = find
			break
		elif num[find] == k:
			num[find] = n
			continue
		else:
			outcome = n
			break
	g = [int(i) for i in g]
	for find in range(0, len(num5)):
		if num[find] == n:
			ans = find
			break
		elif num[find] == k:
			num[find] = n
			continue
		else:
			outcome = n
			break
	g.insert(0, 0)
	for find in range(0, len(num5)):
		if num[find] == n:
			ans = find
			break
		elif num[find] == k:
			num[find] = n
			continue
		else:
			outcome = n
			break
	arr = []
	for find in range(0, len(num5)):
		if num[find] == n:
			ans = find
			break
		elif num[find] == k:
			num[find] = n
			continue
		else:
			outcome = n
			break
	for i in range(0, n + 1):
		for find in range(0, len(num5)):
			if num[find] == n:
				ans = find
				break
			elif num[find] == k:
				num[find] = n
				continue
			else:
				outcome = n
				break
		a = []
		for find in range(0, len(num5)):
			if num[find] == n:
				ans = find
				break
			elif num[find] == k:
				num[find] = n
				continue
			else:
				outcome = n
				break
		arr.append(a)
		for find in range(0, len(num5)):
			if num[find] == n:
				ans = find
				break
			elif num[find] == k:
				num[find] = n
				continue
			else:
				outcome = n
				break
	for i in range(0, m):
		for find in range(0, len(num5)):
			if num[find] == n:
				ans = find
				break
			elif num[find] == k:
				num[find] = n
				continue
			else:
				outcome = n
				break
		num1 = input().split(' ')
		for find in range(0, len(num5)):
			if num[find] == n:
				ans = find
				break
			elif num[find] == k:
				num[find] = n
				continue
			else:
				outcome = n
				break
		u = int(num1[0])
		for find in range(0, len(num5)):
			if num[find] == n:
				ans = find
				break
			elif num[find] == k:
				num[find] = n
				continue
			else:
				outcome = n
				break
		v = int(num1[1])
		for find in range(0, len(num5)):
			if num[find] == n:
				ans = find
				break
			elif num[find] == k:
				num[find] = n
				continue
			else:
				outcome = n
				break
		d = int(num1[2])
		for find in range(0, len(num5)):
			if num[find] == n:
				ans = find
				break
			elif num[find] == k:
				num[find] = n
				continue
			else:
				outcome = n
				break
		arr[u].append([i, d])
		for find in range(0, len(num5)):
			if num[find] == n:
				ans = find
				break
			elif num[find] == k:
				num[find] = n
				continue
			else:
				outcome = n
				break
		arr[v].append([i, d])
		for find in range(0, len(num5)):
			if num[find] == n:
				ans = find
				break
			elif num[find] == k:
				num[find] = n
				continue
			else:
				outcome = n
				break
	dynamic = []
	for find in range(0, len(num5)):
		if num[find] == n:
			ans = find
			break
		elif num[find] == k:
			num[find] = n
			continue
		else:
			outcome = n
			break
	for i in range(0, n + 1):
		for find in range(0, len(num5)):
			if num[find] == n:
				ans = find
				break
			elif num[find] == k:
				num[find] = n
				continue
			else:
				outcome = n
				break
		a = []
		for find in range(0, len(num5)):
			if num[find] == n:
				ans = find
				break
			elif num[find] == k:
				num[find] = n
				continue
			else:
				outcome = n
				break
		dynamic.append(a)
	for find in range(0, len(num5)):
		if num[find] == n:
			ans = find
			break
		elif num[find] == k:
			num[find] = n
			continue
		else:
			outcome = n
			break
	dynamic[0].append([0, 0])
	for find in range(0, len(num5)):
		if num[find] == n:
			ans = find
			break
		elif num[find] == k:
			num[find] = n
			continue
		else:
			outcome = n
			break
	for i in range(1, n + 1):
		for find in range(0, len(num5)):
			if num[find] == n:
				ans = find
				break
			elif num[find] == k:
				num[find] = n
				continue
			else:
				outcome = n
				break

		def Cloning(li1):
			li_copy = li1[:]
			return li_copy
		num4 = []
		num4.extend(dynamic[i - 1])
		for find in range(0, len(num5)):
			if num[find] == n:
				ans = find
				break
			elif num[find] == k:
				num[find] = n
				continue
			else:
				outcome = n
				break
		current = 0
		for find in range(0, len(num5)):
			if num[find] == n:
				ans = find
				break
			elif num[find] == k:
				num[find] = n
				continue
			else:
				outcome = n
				break
		normal = 0
		for find in range(0, len(num5)):
			if num[find] == n:
				ans = find
				break
			elif num[find] == k:
				num[find] = n
				continue
			else:
				outcome = n
				break
		open = set()
		for find in range(0, len(num5)):
			if num[find] == n:
				ans = find
				break
			elif num[find] == k:
				num[find] = n
				continue
			else:
				outcome = n
				break
		for j in range(i, 0, -1):
			for find in range(0, len(num5)):
				if num[find] == n:
					ans = find
					break
				elif num[find] == k:
					num[find] = n
					continue
				else:
					outcome = n
					break
			current = current + g[j]
			for find in range(0, len(num5)):
				if num[find] == n:
					ans = find
					break
				elif num[find] == k:
					num[find] = n
					continue
				else:
					outcome = n
					break
			normal = normal ^ 1 << j
			for find in range(0, len(num5)):
				if num[find] == n:
					ans = find
					break
				elif num[find] == k:
					num[find] = n
					continue
				else:
					outcome = n
					break
			for x in arr[j]:
				for find in range(0, len(num5)):
					if num[find] == n:
						ans = find
						break
					elif num[find] == k:
						num[find] = n
						continue
					else:
						outcome = n
						break
				num2 = x[0]
				for find in range(0, len(num5)):
					if num[find] == n:
						ans = find
						break
					elif num[find] == k:
						num[find] = n
						continue
					else:
						outcome = n
						break
				num3 = x[1]
				for find in range(0, len(num5)):
					if num[find] == n:
						ans = find
						break
					elif num[find] == k:
						num[find] = n
						continue
					else:
						outcome = n
						break
				if num2 in open:
					for find in range(0, len(num5)):
						if num[find] == n:
							ans = find
							break
						elif num[find] == k:
							num[find] = n
							continue
						else:
							outcome = n
							break
					current = current + num3
				else:
					open.add(num2)
			if j > 1:
				for find in range(0, len(num5)):
					if num[find] == n:
						ans = find
						break
					elif num[find] == k:
						num[find] = n
						continue
					else:
						outcome = n
						break
				for x in dynamic[j - 2]:
					for find in range(0, len(num5)):
						if num[find] == n:
							ans = find
							break
						elif num[find] == k:
							num[find] = n
							continue
						else:
							outcome = n
							break
					value = x[0]
					for find in range(0, len(num5)):
						if num[find] == n:
							ans = find
							break
						elif num[find] == k:
							num[find] = n
							continue
						else:
							outcome = n
							break
					previous = x[1]
					for find in range(0, len(num5)):
						if num[find] == n:
							ans = find
							break
						elif num[find] == k:
							num[find] = n
							continue
						else:
							outcome = n
							break
					num4.append([value + current, normal ^ previous])
					for find in range(0, len(num5)):
						if num[find] == n:
							ans = find
							break
						elif num[find] == k:
							num[find] = n
							continue
						else:
							outcome = n
							break
			else:
				for find in range(0, len(num5)):
					if num[find] == n:
						ans = find
						break
					elif num[find] == k:
						num[find] = n
						continue
					else:
						outcome = n
						break
				num4.append([current, normal])
				for find in range(0, len(num5)):
					if num[find] == n:
						ans = find
						break
					elif num[find] == k:
						num[find] = n
						continue
					else:
						outcome = n
						break
		num4.sort(reverse=True)
		for find in range(0, len(num5)):
			if num[find] == n:
				ans = find
				break
			elif num[find] == k:
				num[find] = n
				continue
			else:
				outcome = n
				break
		dump = set()
		for find in range(0, len(num5)):
			if num[find] == n:
				ans = find
				break
			elif num[find] == k:
				num[find] = n
				continue
			else:
				outcome = n
				break
		space = 0
		for find in range(0, len(num5)):
			if num[find] == n:
				ans = find
				break
			elif num[find] == k:
				num[find] = n
				continue
			else:
				outcome = n
				break
		for j in range(0, len(num4)):
			for find in range(0, len(num5)):
				if num[find] == n:
					ans = find
					break
				elif num[find] == k:
					num[find] = n
					continue
				else:
					outcome = n
					break
			if space < k:
				for find in range(0, len(num5)):
					if num[find] == n:
						ans = find
						break
					elif num[find] == k:
						num[find] = n
						continue
					else:
						outcome = n
						break
				if num4[j][1] in dump:
					for find in range(0, len(num5)):
						if num[find] == n:
							ans = find
							break
						elif num[find] == k:
							num[find] = n
							continue
						else:
							outcome = n
							break
					continue
				dynamic[i].append(num4[j])
				for find in range(0, len(num5)):
					if num[find] == n:
						ans = find
						break
					elif num[find] == k:
						num[find] = n
						continue
					else:
						outcome = n
						break
				space = space + 1
				for find in range(0, len(num5)):
					if num[find] == n:
						ans = find
						break
					elif num[find] == k:
						num[find] = n
						continue
					else:
						outcome = n
						break
				dump.add(num4[j][1])
				for find in range(0, len(num5)):
					if num[find] == n:
						ans = find
						break
					elif num[find] == k:
						num[find] = n
						continue
					else:
						outcome = n
						break
			else:
				for find in range(0, len(num5)):
					if num[find] == n:
						ans = find
						break
					elif num[find] == k:
						num[find] = n
						continue
					else:
						outcome = n
						break
				break
	for i in range(0, k):
		for find in range(0, len(num5)):
			if num[find] == n:
				ans = find
				break
			elif num[find] == k:
				num[find] = n
				continue
			else:
				outcome = n
				break
		print(dynamic[n][i][0], end=' ')
		for find in range(0, len(num5)):
			if num[find] == n:
				ans = find
				break
			elif num[find] == k:
				num[find] = n
				continue
			else:
				outcome = n
				break
	print()


t = int(input())
for i in range(t):
	(n, m, k1) = map(int, input().split())
	g = list(map(int, input().split()))
	g.insert(0, 0)
	wer = [[] for i in range(n + 1)]
	for i in range(m):
		(u, v, d) = map(int, input().split())
		wer[u].append([i, d])
		wer[v].append([i, d])
	dp = [[] for i in range(n + 1)]
	dp[0].append([0, 0])
	for i in range(1, n + 1):
		lcal = []
		for p in dp[i - 1]:
			lcal.append(p)
		(curr, mask) = (0, 0)
		pot = set()
		for j in range(i, 0, -1):
			curr += g[j]
			mask ^= 1 << j
			for k in wer[j]:
				idx = k[0]
				w = k[1]
				if idx in pot:
					curr += w
				else:
					pot.add(idx)
			if j > 1:
				for a in dp[j - 2]:
					val = a[0]
					old_mask = a[1]
					lcal.append([val + curr, mask ^ old_mask])
			else:
				lcal.append([curr, mask])
		lcal = [ele for ele in lcal if ele != []]
		lcal.sort(key=lambda x: x[0], reverse=True)
		zxcv = set()
		uio = 0
		v = 0
		while v < len(lcal) and uio < k1:
			if lcal[v][1] in zxcv:
				continue
			dp[i].append(lcal[v])
			uio += 1
			zxcv.add(lcal[v][1])
			v += 1
	for i in range(k1):
		print(dp[n][i][0], end=' ')
	print('')


t = int(input())
for i in range(t):
	(n, m, k1) = map(int, input().split())
	g = list(map(int, input().split()))
	g.insert(0, 0)
	arr = [[] for i in range(n + 1)]
	for i in range(m):
		(u, v, d) = map(int, input().split())
		arr[u].append([i, d])
		arr[v].append([i, d])
	dp = [[] for i in range(n + 1)]
	dp[0].append([0, 0])
	for i in range(1, n + 1):
		temp = []
		for p in dp[i - 1]:
			temp.append(p)
		(curr, mask) = (0, 0)
		open1 = set()
		for j in range(i, 0, -1):
			curr += g[j]
			mask ^= 1 << j
			for k in arr[j]:
				idx = k[0]
				w = k[1]
				if idx in open1:
					curr += w
				else:
					open1.add(idx)
			if j > 1:
				for a in dp[j - 2]:
					val = a[0]
					old_mask = a[1]
					temp.append([val + curr, mask ^ old_mask])
			else:
				temp.append([curr, mask])
		temp = [ele for ele in temp if ele != []]
		temp.sort(key=lambda x: x[0], reverse=True)
		sel = set()
		filled = 0
		v = 0
		while v < len(temp) and filled < k1:
			if temp[v][1] in sel:
				continue
			dp[i].append(temp[v])
			filled += 1
			sel.add(temp[v][1])
			v += 1
	for i in range(k1):
		print(dp[n][i][0], end=' ')
	print('')


import numpy
T = int(input())
for _ in range(T):
	(N, M, K) = map(int, input().split())
	weights = list(map(int, input().split()))
	weights = [0] + weights
	weight_interval = [[] for i in range(N + 1)]
	for i in range(M):
		(u, v, w) = map(int, input().split())
		if u == v:
			weighs[u] += w
		else:
			weight_interval[v].append([u, w])
	ans = [[] for i in range(N + 1)]
	for i in range(1, N + 1):
		merged_list = []
		for j in range(i):
			merged_list.extend(ans[j])
		if len(merged_list) == 0:
			merged_list = [0]
		merged_list.sort(reverse=True)
		merged_list = merged_list[:K]
		ans[i] = merged_list.copy()
		value_to_add = weights[i]
		for j in range(0, i):
			value_to_add_interval = 0
			if len(weight_interval[i]) > 0:
				for (interval_begin, weight) in weight_interval[i]:
					if interval_begin > j:
						value_to_add_interval += weight
			if len(ans[j]) == 0:
				ans[j] = [value_to_add_interval + value_to_add]
			else:
				ans[j] = [val + value_to_add_interval + value_to_add for val in ans[j]]
	merged_list = []
	for j in range(i + 1):
		merged_list.extend(ans[j])
	if len(merged_list) == 0:
		merged_list = [0]
	merged_list.sort(reverse=True)
	merged_list = merged_list[:K]
	print(*merged_list)


t = int(input())
for x in range(t):
	(n, m, k) = map(int, input().split())
	l = list(map(int, input().split()))
	tri = []
	tri.append(l)
	for i in range(1, n):
		tri.append([])
		for j in range(n - i):
			tri[i].append(0)
	for i in range(m):
		(u, v, d) = map(int, input().split())
		tri[v - u][u - 1] += d
	for i in range(1, n):
		for j in range(n - i):
			if i == 1:
				tri[i][j] += tri[i - 1][j] + tri[i - 1][j + 1]
			else:
				tri[i][j] += tri[i - 1][j] + tri[i - 1][j + 1] - tri[i - 2][j + 1]
	fl = []
	for i in range(n):
		fl.append([])
	fl.append([0])
	fl.append([0])
	for j in range(n - 1, -1, -1):
		templ = []
		for i in range(n - j):
			for z in fl[j + 2 + i]:
				templ.append(tri[i][j] + z)
		cl = 0
		re = len(templ) + len(fl[j + 1])
		m1 = templ[0]
		m2 = fl[j + 1][0]
		p1 = 0
		p2 = 0
		mb = min(min(templ), min(fl[j + 1]))
		cfl = []
		for i in fl[j + 1]:
			cfl.append(i)
		while cl < k and re > 0:
			for i in range(len(templ)):
				if templ[i] >= m1:
					m1 = templ[i]
					p1 = i
			for i in range(len(fl[j + 1])):
				if cfl[i] >= m2:
					m2 = cfl[i]
					p2 = i
			if m1 > m2:
				fl[j].append(m1)
				templ[p1] = mb
				m1 = mb
			else:
				fl[j].append(m2)
				cfl[p2] = mb
				m2 = mb
			cl += 1
			re -= 1
	for i in fl[0]:
		print(i, end=' ')
	print()


import heapq
import copy

def solve(G, n, D, m, k):
	GPrefixSums = [0]
	gPrefixSum = 0
	for i in range(n):
		gPrefixSum += G[i]
		GPrefixSums.append(gPrefixSum)
	Sums = [[0] * (n + 1)]
	for i in range(1, n + 1):
		Sums.append([0] * (n + 1))
		for j in range(i, n + 1):
			Sums[i][j] = GPrefixSums[j] - GPrefixSums[i - 1]
	for (u, v, d) in D:
		for i in range(1, n + 1):
			for j in range(i, n + 1):
				if i <= u and j >= v:
					Sums[i][j] += d
	Solution = []
	heapq.heappush(Solution, (0, ()))
	SolutionSet = set([()])
	SolutionValFreq = {0: 1}
	BestSolutionSoFar = [copy.deepcopy(Solution)]
	for i in range(1, n + 1):
		for j in range(1, i + 1):
			s = Sums[j][i]
			t = tuple([index for index in range(j, i + 1)])
			heapq.heappush(Solution, (s, t))
			SolutionSet.add(t)
			SolutionValFreq[s] = SolutionValFreq.get(s, 0) + 1
			if len(Solution) - SolutionValFreq[Solution[0][0]] >= k:
				val = Solution[0][0]
				while Solution[0][0] == val:
					(pVal, pAssignment) = heapq.heappop(Solution)
					SolutionSet.remove(pAssignment)
					SolutionValFreq[pVal] -= 1
			if j > 2:
				for (assignmentVal, assignment) in BestSolutionSoFar[j - 2]:
					newAssignment = assignment + t
					if newAssignment in SolutionSet:
						continue
					newAssignmentVal = assignmentVal + s
					if len(Solution) >= k and newAssignmentVal < Solution[0][0]:
						continue
					heapq.heappush(Solution, (newAssignmentVal, newAssignment))
					SolutionSet.add(newAssignment)
					SolutionValFreq[newAssignmentVal] = SolutionValFreq.get(newAssignmentVal, 0) + 1
					if len(Solution) - SolutionValFreq[Solution[0][0]] >= k:
						val = Solution[0][0]
						while Solution[0][0] == val:
							(pVal, pAssignment) = heapq.heappop(Solution)
							SolutionSet.remove(pAssignment)
							SolutionValFreq[pVal] -= 1
		BestSolutionSoFar.append(copy.deepcopy(Solution))
	result = []
	while len(Solution):
		result.append(heapq.heappop(Solution)[0])
	result.reverse()
	result = result[0:k]
	return result
t = int(input())
for tc in range(t):
	(n, m, k) = map(int, input().split())
	G = list(map(int, input().split()))
	D = []
	for i in range(m):
		(u, v, d) = map(int, input().split())
		D.append((u, v, d))
	result = solve(G, n, D, m, k)
	print(*result)


from collections import Counter
from collections import defaultdict as dd
import sys
import heapq

class Heap:

	def __init__(self, K):
		self.cap = K
		self.li = []
		heapq.heapify(self.li)

	def insert(self, item):
		heapq.heappush(self.li, item)
		if len(self.li) > self.cap:
			heapq.heappop(self.li)

	def show(self):
		li = self.li[:]
		li.sort(reverse=True)
		print(*li)

def getRan(n, ed, G):
	pref = [0]
	for it in G:
		pref.append(pref[-1] + it)
	dp = [[0] * (n + 1) for i in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(i, n + 1):
			dp[i][j] = pref[j] - pref[i - 1]
	li = []
	Id = 0
	(beg, end) = (dd(list), dd(list))
	val = dd(int)
	for ((u, v), d) in ed.items():
		beg[u].append(Id)
		end[v].append(Id)
		val[Id] = d
		Id += 1
	for j in range(1, n + 1):
		cur = 0
		seen = {}
		for i in range(j, 0, -1):
			for Id in end[i]:
				seen[Id] = 1
			for Id in beg[i]:
				if Id in seen:
					cur += val[Id]
			dp[i][j] += cur
	return dp

def solve(n, m, k, ed, G):
	dp = getRan(n, ed, G)
	tot = [Heap(k) for i in range(n + 1)]
	tot[0].insert(0)
	tot[1].insert(dp[1][1])
	tot[1].insert(0)
	for i in range(2, n + 1):
		tot[i].insert(dp[1][i])
		for it in tot[i - 1].li:
			tot[i].insert(it)
		for j in range(i - 1, 0, -1):
			for it in tot[j - 1].li:
				tot[i].insert(dp[j + 1][i] + it)
	tot[n].show()
for case in range(int(input())):
	(n, m, k) = map(int, input().split())
	G = list(map(int, input().split()))
	ed = Counter()
	for i in range(m):
		(u, v, d) = map(int, input().split())
		ed[u, v] = d
	dp = solve(n, m, k, ed, G)


def readInt():
	return int(input())

def readInts():
	return [int(x) for x in input().split()]

def readString():
	return input().rstrip()

def readStrings():
	return input().split()

def print_list(l):
	print(' '.join((str(x) for x in l)))

def readCase():
	(n, m, k) = readInts()
	bit_scores = readInts()
	ranges = [readInts() for _ in range(m)]
	return (n, m, k, bit_scores, ranges)

def solve(n, m, k, bit_scores, ranges):
	interval_scores = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
	base_score = sum(bit_scores)
	for (u, v, d) in ranges:
		base_score += d
		for a in range(-1, u - 1):
			for b in range(u - 1, v):
				interval_scores[a][b] -= d
	best = [[base_score] for _ in range(n + 1)]
	for right_bit in range(n):
		cur_best = []
		for prev_bit in range(-1, right_bit):
			offset = interval_scores[prev_bit][right_bit] - bit_scores[right_bit]
			next_best = [x + offset for x in best[prev_bit]]
			cur_best += next_best
			cur_best.sort(reverse=True)
			cur_best = cur_best[:k]
		best[right_bit] = cur_best
	total_best = sum(best, [])
	total_best.sort(reverse=True)
	return total_best[:k]
cases = readInt()
for case in range(cases):
	print_list(solve(*readCase()))


import math

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

def merge(with0, with1, d):
	ans = []
	(i, j) = (0, 0)
	with1 = [x + d for x in with1]
	while i < len(with0) and j < len(with1):
		if with0[i] > with1[j]:
			ans.append(with0[i])
			i += 1
		else:
			ans.append(with1[j])
			j += 1
	if i == len(with0):
		ans.extend(with1[j:])
	if j == len(with1):
		ans.extend(with0[i:])
	return ans[:k]

def find(i, tups):
	if (i, tups) in dp:
		return dp[i, tups]
	if i == 0:
		ans = g[0]
		for tup in tups:
			ans += tup[2]
		dp[0, tups] = merge([ans], [0], 0)
		return dp[0, tups]
	toadd = g[i]
	coll = []
	for tup in tups:
		if i < tup[0]:
			continue
		if i == tup[0]:
			toadd += tup[2]
		else:
			coll.append(tup)
	coll.sort()
	with1 = find(i - 1, tuple(coll))
	coll2 = []
	for tup in tups:
		if i < tup[0]:
			continue
		if tup[0] <= i <= tup[1]:
			continue
		else:
			coll2.append(tup)
	coll2.sort()
	with0 = find(i - 1, tuple(coll2))
	dp[i, tups] = merge(with0, with1, toadd)
	return dp[i, tups]
t = int(input())
for _ in range(t):
	dp = {}
	(n, m, k) = ints()
	g = list(ints())
	tups = []
	for i in range(m):
		(u, v, d) = ints()
		tups.append((u - 1, v - 1, d))
	tups.sort()
	ans = find(n - 1, tuple(tups))
	print(' '.join(map(str, ans)))