给你一个长度为 $n$ 的整数序列：$a_1, a_2, \ldots, a_n$。$a$ 中的每个元素都是 $1$、$2$ 或 $3$。

序列中的每个元素都有一个美丽值，用正整数表示。第 $i$ 个元素的美丽值为 $b_i$。

你可以进行任意多次以下操作：选择该序列的一个子段（连续子序列），如果该子段的元素之和为 $4$ 或 $8$，则可以将其删除。每次操作后，剩余的左侧和右侧部分会重新拼接在一起，形成一个连续的序列。

你的任务是最小化操作后剩余元素的和。如果有多种方案可以达到最小值，你应当最大化剩余元素的美丽值之和。

输入格式

第一行包含一个整数 $t$，表示测试用例的数量（$1 \leq t \leq 2000$）。

每个测试用例包含四行：

• 第一行包含一个整数 $n$，表示原始序列的长度（$1 \le n \le 3 \cdot 10^5$）。
• 第二行包含一个无空格的字符串 $a_1 a_2 \ldots a_n$，表示原始序列。字符串中的每个字符都是 $1$、$2$ 或 $3$。
• 第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$，表示序列中每个元素的美丽值（$1 \leq b_i \leq 99$）。
• 第四行包含一个整数 $p$，表示测试用例的类型（$1 \leq p \leq 2$）。

所有测试用例的 $n$ 之和不超过 $3 \cdot 10^5$。

输出格式

对于每个测试用例，输出剩余数字的最小和以及剩余数字的最大美丽值之和。如果测试用例的 $p = 1$，则只需输出这两个值。

如果 $p = 2$，你还需要输出达到这些值所需的操作序列。在下一行中，输出操作次数 $k$。在接下来的 $k$ 行中，输出关于每次操作的信息。其中的第 $i$ 行，首先输出第 $i$ 次操作中删除的元素个数，然后按升序输出它们在初始序列中的下标。在每次操作中，被删除的元素在紧接该操作执行前必须构成序列中的一个子段。

样例

输入 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

输出 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