#753 Fat Sequence

Statement

Statement language

You are given a sequence $A = [A_1, A_2, \cdots, A_N]$ of length $N$ .

Choose indices $1 \leq i_1 < i_2 < \cdots < i_k \leq N$ . If the sequence satisfies , it is called an of . Its length is .

Consider the increasing subsequences of $A$ with the maximum length. Among them, the one with the largest sum of elements is called the fat sequence of $A$ .

Find the fat sequence of $A$ and the sum of its elements.

Input

The input is given from Standard Input in the following format:

$T$ case $_1$ case $_2$

Output

For each test case, print the following two lines.

On the first line, print the elements of the fat sequence of $A$ in order, separated by spaces.

On the second line, print the sum of the elements of the fat sequence of $A$ .

If there are multiple solutions, print any of them.

Constraints

$1 \leq T \leq 100\,000$ .
$1 \leq N \leq 1\,000\,000$ .
().

Subtasks

#	Score	Constraints
1	8	$N \leq 10$ . The sum of $N$ over all test cases is at most $10\,000$ .
2	22	$N \leq 5\,000$ .

Samples

Input

4
6
10 20 10 30 20 50
7
3 1 4 1 5 9 2
5
5 5 4 4 3
1
1000000000

Output

10 20 30 50
110
3 4 5 9
21
5
5
1000000000
1000000000

In the first case, $[10, 20, 30, 50]$ is the only longest increasing subsequence.

In the second case, the longest increasing subsequences have length $4$ . They are $[3, 4, 5, 9]$ and , with sums and .