One, Two, Three

길이가 $N$인 수열 $a_1,a_2,\ldots ,a_N$이 주어진다. $a$의 각 원소는 $1$, $2$, 또는 $3$이다.

각 원소는 양의 정수로 나타나는 아름다움을 가지고 있다. $i$번째 원소의 아름다움은 $b_i$로 나타난다.

선택한 구간 안에 있는 원소의 합이 $4$ 혹은 $8$이면 구간 내 원소들을 제거하는 시행을 원하는 만큼 할 수 있다.

남아있는 원소들의 합을 최소화 하려고 한다. 만약 원소들의 합을 최소화시키는 방법이 여러 가지 있다면, 남아있는 원소들의 아름다움의 합을 최대화 하려고 한다.

수열에 원하는 만큼 시행을 하여 남아있는 원소들의 합을 최소화해보자. 만약 남아있는 원소들의 합을 최소화시키는 방법이 여러 가지 있다면, 남아있는 원소들의 아름다움의 합을 최대화하자. 모든 테스트 케이스에 대해서 실행한 시행의 목록을 출력하지 않아도 됨에 유의하라.

각 입력은 여러 개의 테스트 케이스로 이루어져 있다. 첫 번째 줄에는 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스는 4개의 줄로 이루어져 있다.

• 첫 번째 줄에는 수열의 길이를 나타내는 정수 $N$이 주어진다.
• 두 번째 줄에는 처음 수열을 나타내는 문자열 $a_1a_2\ldots a_N$이 주어진다. 각 문자는 $1$, $2$, $3$ 중 하나이다.
• 세 번째 줄에는 각 원소의 아름다움을 나타내는 $N$개의 정수 $b_1,b_2,\ldots ,b_N$이 공백으로 구분되어 주어진다.
• 네 번째 줄에는 테스트 케이스의 유형을 나타내는 정수 $p$가 주어진다. $p=1$인 테스트 케이스의 경우, 남아있는 원소의 합의 최솟값과 남아있는 원소들의 아름다움의 합의 최댓값만 출력하면 된다. $p=2$인 경우에는 실행한 시행들의 목록도 출력해야 한다.

각 테스트 케이스에 대해서, 첫 번째 줄에 남아있는 원소들의 합의 최솟값과 남아있는 원소들의 아름다움의 합의 최댓값을 출력한다.

$p=2$인 경우에, 실행한 시행들의 목록도 출력해야 한다. 두 번째 줄에 실행한 시행의 개수 $K$를 출력한다.

다음에 이어지는 $K$개의 줄에는 각 시행에 대해 출력해야 한다. $i$번째 줄에는 $i$번째 시행에 제거한 원소의 개수를 출력한다. 그리고 제거한 원소들의 위치를 오름차순으로 출력한다. 각 시행마다 제거한 원소들은 $i$번째 시행을 실행하기 전에 수열에서 구간을 이루어야 한다. 제거한 원소들의 위치를 출력할 때 처음에 주어진 수열에서의 위치를 출력해야 한다.

• $1\leq T\leq 2\, 000$
• 각 테스트 케이스에 대해 $N\geq 1$
• $\sum N\leq 3\times 10^5$
• 각 테스트 케이스에 대해 $1\leq a_i\leq 3$ ($1\leq i\leq N$)
• 각 테스트 케이스에 대해 $1\leq b_i\leq 99$ ($1\leq i\leq N$)
• 각 테스트 케이스에 대해 $1\leq p\leq 2$