Given a sequence $A$, each element $A_i$ in the sequence has a deletion cost $B_i$ and an additional attribute $C_i$. Please delete a subset of elements such that the length of the Longest Increasing Subsequence (LIS) of $A$ decreases by at least 1, while minimizing the total deletion cost. Output the solution.

If there are multiple solutions, output the one that is lexicographically smallest after sorting the additional attributes of the deleted elements.

Input

The input contains multiple test cases. The first line contains an integer $T$, representing the number of test cases. The next $4T$ lines describe each test case. The first line of each test case contains an integer $N$, representing the number of elements in $A$. The next three lines each contain $N$ integers $A_1 \dots A_n$, $B_1 \dots B_n$, and $C_1 \dots C_n$, satisfying $1 \le A_i, B_i, C_i \le 10^9$, and all $C_i$ are distinct.

Output

For each test case, output two lines. The first line contains two integers $S, M$, representing the total deletion cost and the number of deleted elements, respectively. The next line contains $M$ integers, representing the indices of the deleted elements in $A$, in ascending order.

Examples

Input 1

1
6
3 4 4 2 2 3
2 1 1 1 1 2
6 5 4 3 2 1

Output 1

4 3
2 3 6

Note

Explanation: Deleting $\{A_2, A_3, A_6\}$, $\{A_1, A_6\}$, $\{A_2, A_3, A_4, A_5\}$ are all valid solutions, but the one corresponding to $\{A_2, A_3, A_6\}$ has the lexicographically smallest $C$ values.

Subtasks

For each test case: If the participant's output follows the output format and all $S$ values match the answer, they can receive 30% of the points for that test case. If the participant's $S$ values match the answer and all output solutions are valid, they can receive 50% of the points. * If the participant's output is exactly the same as the answer, they can receive 100% of the points.

The final score is calculated based on the highest-scoring criteria met by the participant's output.

Vector Set

Description

Maintain a set of vectors and support the following operations online: "A $x$ $y$ ($|x|, |y| \le 10^8$)": Add a vector $(x, y)$. "Q $x$ $y$ $l$ $r$ ($|x|, |y| \le 10^8, 1 \le l \le r \le T$, where $T$ is the number of vectors already added)": Query the maximum dot product of the vectors added from the $l$-th to the $r$-th with vector $(x, y)$.

The set is initially empty.

Input

The first line contains an integer $N$ and a character $s$, representing the number of operations and the data type, respectively. The next $N$ lines each contain an operation, formatted as described above.

Please note that when $s \neq \text{'E'}$, all integers in the input are encrypted. You can use the following code to obtain the original input:

inline int decode (int x, long long lastans) {
return x ^ (lastans & 0x7fffffff);
}

function decode (x : longint; lastans : int64) : longint; 
begin
decode := x xor (lastans and $7fffffff);
end;

Where $x$ is the number read by the program, and $lastans$ is the answer to the last query. Before the first query, $lastans = 0$.

Note

The dot product of vectors $(x, y)$ and $(z, w)$ is defined as $xz + yw$.