给定一个长度为 \(n\) 的字符串表示一个序列 \(a_i\)，字符串中只有 '+'、'-'，第 \(i\) 个字符为 '+' 表示 \(a_i = 1\)，为 '-' 表示 \(a_i = -1\)。\(q\) 组询问，每组询问给定两个整数 \(l, r\,(1\le l\le r\le n)\)，将 \(a_{l\sim r}\) 单独取出后，求最少删除多少个数字，使得所成长度为 \(m\) 的序列 \(\left\{b_{i}\right\}\) 满足 \(\sum_{i=1}^m(-1)^{i-1}b_i=0\)。
D1 仅要求出最少删除多少个数字，D2 需要求出删除哪些数字（多解输出任意一组即可）。
\(T\) 组数据，\(1\le T\le 10^3, 1\le n, q\le 3\cdot 10^5\)。
先考虑没有多组询问。
窝萌首先发现一个性质，那就是如果有两个连续的相同字符，那么这两个字符对答案无贡献，我们可以直接删掉。那我们一次删掉之后，最后得到的序列只能是正负交替的了。于是我们只要考虑此种情况即可。我们发现如果删完的序列长度为奇数的话，我们只要删除最中间那个数就可以了。我们考虑偶数，如果长度已经为 \(0\)，那显然就不用删除了，如果不为 \(0\) 的话，考虑到们此相同字符消除一定是两个两个删的，所以至少要删两个数，有考虑到如果随便删一个数，那么序列长度就变成奇数了，所以我们只需要删两个数即可。
于是我们发现，如果是询问系列长度为奇数，那答案最多是 \(1\)，如果是偶数，我们可以维护前缀和 \(S_i=\sum_{j=1}^i(-1)^{j-1}a_j\)，如果 \(S_r-S_{l-1}\) 是 \(0\)，那答案就是 \(0\)，否则是 \(2\)。
这样 D1 就做完了。
我们考虑 D2，我们先考虑奇数的情况，我们假设要删掉的数是第 \(k\) 个，那我们有 \(\sum_{i=l}^{k - 1}(-1)^{i-1}a_{i}+(-1)\cdot\sum_{i=k+1}^r(-1)^{i-1}a_i=0\) 也即 \(S_{k-1}-S_{l-1}=S_{r}-S_{k}\) 也即 \(S_{k-1}+S_k=S_{l-1}+S_r\)，于是我们对每个 \(S_{k-1}+S_k\) 相同的开个 set，之后对每组询问 \(\left<l,r\right>\)，我们只要在所有 \(S_{k-1}+S_k=S_{l-1}+S_r\) 数中 lower_bound 出一个在 \([l,r]\) 中的答案即可。
长度为偶数就直接随便删掉最左边或是最右边的数，然后按照奇数的方法做即可。
const int maxn = 300005;
int qzh[maxn];
char s[maxn];
void solve() {
int n, q;
scanf("%d%d%s", &n, &q, s + 1);
std::map<int, std::set<int>> mp;
for (int i = 1; i <= n; ++i) {
qzh[i] = qzh[i - 1] + (((i & 1) == (s[i] == '+')) ? 1 : -1);
mp[qzh[i - 1] + qzh[i]].insert(i);
}
while (q--) {
int l, r;
scanf("%d%d", &l, &r);
if (qzh[r] - qzh[l - 1]) {
if ((r - l) & 1) {
puts("2");
writesp(r);
r--;
} else {
puts("1");
}
writeln(*mp[qzh[l - 1] + qzh[r]].lower_bound(l));
} else {
puts("0");
}
}
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}