#P2216. 资料归档

资料归档

本题需要文件读写

文件 IO 为:输入文件 archive.in,输出文件 archive.out。请使用上述文件名读入和输出。

问题描述

市科技馆收到 nn 份活动资料,编号依次为 1,2,…,n1,2,\ldots,n。工作人员需要为资料办理登记,登记机还带有一个可以临时存放资料的收纳盒。开始时,收纳盒是空的。

工作人员按编号从小到大处理资料。处理第 ii 份资料时,根据操作记录 sis_i,执行以下三种操作之一:

  • si=1s_i=\mathtt{1}:暂存资料。把第 ii 份资料放入收纳盒,叠在盒内所有资料的最上方,不办理登记。
  • si=2s_i=\mathtt{2}:优先办理盒内资料。如果收纳盒非空,取出最上方的一份资料,为它办理登记;否则,为第 ii 份资料办理登记。
  • si=3s_i=\mathtt{3}:直接办理。为第 ii 份资料办理登记,不改变收纳盒中的资料。

每个编号只对应一次操作。当操作 2\mathtt{2} 办理了盒内的其他资料时,第 ii 份资料不会自动暂存,也不会被办理登记。全部操作结束后,收纳盒中的资料也不会自动办理登记。

给定完整操作记录,请找出所有未办理登记的资料编号。

输入格式

第一行包含一个正整数 TT,表示测试用例数。本题固定 T=10T=10。

对于每个测试用例:

第一行输入一个正整数 nn。

第二行输入一个长度为 nn、仅由字符 1、2、3 组成的字符串 ss。

输出格式

对于每个测试用例,输出两行。

第一行输出未办理登记的资料数量 kk。第二行按升序输出这些资料的编号,编号之间用一个空格隔开。如果 k=0k=0,第二行仍需输出一个空行。

样例输入 1

10
2
12
2
13
2
23
6
112332
3
112
6
211213
1
1
1
2
1
3
6
111222

样例输出 1

1
2
1
1
0

2
3 6
2
1 3
3
2 4 5
1
1
0

0

3
4 5 6

说明

公开分档大样例:下载 samples.zip。

评测数据规模

对于 100%100\% 的数据,保证 T=10T=10,1≤n≤2×1051\le n\le2\times10^5。同一输入文件中所有测试用例的 nn 之和不超过 2×1052\times10^5。

下表中的 ∑n\sum n 表示同一输入文件中所有测试用例的 nn 之和。

各测试点的附加限制如下表所示:

测试点编号 n≤n\le ∑n≤\sum n\le 特殊性质
1∼61\sim6 200200 20002000 无
7∼107\sim10 2×1052\times10^5 A
11∼1411\sim14 B
15∼2015\sim20 无
  • 特殊性质 A:字符串 ss 中不出现字符 1。
  • 特殊性质 B:字符串 ss 中不出现字符 2。

本题共 2020 个独立测试点,每点 55 分。