You are given a sequence of $n$ integers: $a_1, a_2, \ldots, a_n$. Each element of $a$ is either $1$, $2$, or $3$.

Each element of the sequence has a beauty, expressed as a positive integer. The $i$-th element has a beauty of $b_i$.

You can apply the following operation as many times as you want: choose a subsegment (contiguous subsequence) of the sequence and remove it if the sum of its elements is $4$ or $8$. After each operation, the remaining left and right parts are glued together to form a contiguous sequence again.

Your task is to minimize the sum of the remaining elements after applying the operations. If there are several ways to do so, you should maximize the sum of the beauty of the remaining elements.

Input

The first line contains an integer $t$, the number of test cases ($1 \leq t \leq 2000$).

Each test case consists of four lines: The first line contains an integer $n$, the length of the original sequence ($1 \le n \le 3 \cdot 10^5$). The second line contains a string $a_1 a_2 \ldots a_n$ without spaces, representing the original sequence. Each character of the string is either $1$, $2$, or $3$. The third line contains $n$ integers $b_1, b_2, \ldots, b_n$: the beauty of each element in the sequence ($1 \leq b_i \leq 99$). The fourth line contains an integer $p$, the type of the test case ($1 \leq p \leq 2$).

The sum of $n$ over all test cases does not exceed $3 \cdot 10^5$.

Output

For each test case, print the minimum sum of the remaining numbers and the maximum sum of the beauties of the remaining numbers. If $p = 1$ for a test case, this is enough.

If $p = 2$, you should additionally print the sequence of operations that achieves these values. On the next line, print $k$, the number of operations. In the following $k$ lines, you should print the information about the operations. On the $i$-th line among them, first, print the number of elements removed in the $i$-th operation, and next, print their indices in increasing order. The indices should be as they were in the initial sequence. In each operation, the removed elements should form a subsegment in the sequence just before applying this operation.

Examples

Input 1

6
3
121
1 2 3
2
3
221
4 5 6
2
3
123
7 8 9
1
6
123221
10 11 12 13 14 15
2
6
312322
15 14 13 12 11 10
2
6
213312
9 8 7 5 5 1
2

Output 1

0 0
1
3 1 2 3 
1 6
1
2 1 2 
6 24
3 29
1
4 1 2 3 4 
5 25
2
2 5 6 
2 1 2 
0 0
3
2 2 3 
2 4 5 
2 1 6