B. Reverse Sort
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Ashish has a binary string s
of length n
that he wants to sort in non-decreasing order.
He can perform the following operation:
Choose a subsequence of any length such that its elements are in non-increasing order. Formally, choose any k
such that 1≤k≤n and any sequence of k indices 1≤i1<i2<…<ik≤n such that si1≥si2≥…≥sik
.
Reverse this subsequence in-place. Formally, swap si1
with sik, swap si2 with sik−1, … and swap si⌊k/2⌋ with si⌈k/2⌉+1 (Here ⌊x⌋ denotes the largest integer not exceeding x, and ⌈x⌉ denotes the smallest integer not less than x
)
Find the minimum number of operations required to sort the string in non-decreasing order. It can be proven that it is always possible to sort the given binary string in at most n
operations.
Input
The first line contains a single integer t
(1≤t≤1000)
— the number of test cases. The description of the test cases follows.
The first line of each test case contains an integer n
(1≤n≤1000) — the length of the binary string s
.
The second line of each test case contains a binary string s
of length n containing only 0s and 1
s.
It is guaranteed that the sum of n
over all test cases does not exceed 1000
.
Output
For each test case output the following:
The minimum number of operations m
in the first line (0≤m≤n
).
Each of the following m
lines should be of the form: k i1 i2 ... ik, where k is the length and i1<i2<...<ik
are the indices of the chosen subsequence. For them the conditions from the statement must hold.
Example
Input
Copy
3
7
0011111
5
10100
6
001000
Output
Copy
0
1
4 1 3 4 5
1
3 3 5 6
Note
In the first test case, the binary string is already sorted in non-decreasing order.
In the second test case, we can perform the following operation:
k=4:
choose the indices {1,3,4,5}
1–
0 1– 0– 0– → 0– 0 0– 1– 1–
In the third test case, we can perform the following operation:
k=3:
choose the indices {3,5,6}
0
0 1– 0 0– 0– → 0 0 0– 0 0– 1–
0 Comments