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$.

见题面

见题面