题目
Description
“人类智慧的冰峰,只有萌萌哒的我寂寞地守望。”
——TB
TB正走在改造人类智慧基因的路上。
TB发现人类智慧基因一点也不萌萌哒,导致人类普遍智商过低,为了拯救低智商人群,博爱的TB开始改造人类智慧基因。
人类智慧DNA由$C$种人类智慧脱氧核苷酸构成(这是一种十分特殊的DNA)。TB智慧DNA片段$T$长度为$M$,她可以把另一段长度为$M$的人类智慧DNA片段$S$改造成$T$。改造过程中,TB可以充分发挥智慧,将任意两种人类智慧脱氧核苷酸交换(比如对于片段$S=12321$,交换$1$和$2$变成 $S=21312$,交换$1$和$4$变成$42324$),可以无限次交换。如果$S$可以通过若干次交换变成$T$,那么就称$S$为“萌萌哒人类基因片段”。
TB想知道对于一个长度为$N$的人类智慧DNA片段$S[1 \sim N]$,有多少个长度为$M$的连续子片段$S[i \sim i+M-1]$,是“萌萌哒人类基因片段”, 且这些“萌萌哒人类基因片段”在哪里。
Input
输入文件名为reform.in。
输入文件的第一行包含两个正整数$case$和$C$,分别表示数据组数和人类智慧脱氧核苷酸的种数。
接下来$3 \times case$行, 每三行表示一组数据:
第一行两个正整数$N$和$M$,表示人类智慧DNA片段$S$和TB智慧DNA片段$T$的长度。
第二行$N$个正整数,表示人类智慧DNA片段$S$。
第三行$M$个正整数,表示TB智慧DNA片段$T$。
Output
输出文件名为reform.out。
对于每组数据:
第一行一个正整数$tot$,表示“萌萌哒人类基因片段”的个数。
接下来一行$tot$个用空格隔开的正整数$pos$,表示“萌萌哒人类基因片段”开头所在的位置。要求从小到大输出每个$pos$。
Sample Input
3 3
6 3
1 2 1 2 3 2
3 1 3
6 3
1 2 1 2 1 2
3 1 3
6 3
1 1 2 1 2 1
3 1 3
SampleOutput
3
1 2 4
4
1 2 3 4
3
2 3 4
对于第一组数据:
- $S[1 \sim 3]=121$,可以先将$1$和$2$交换变成$212$,再将$2$和$3$交换变成$313$。
- $S[2 \sim 4]=212$,可以将$2$和$3$交换变成$313$。
- $S[4 \sim 6]=232$,可以先将$2$和$3$交换变成$323$,再将$1$和$2$交换变成$313$。
Hint
测试点编号 | $n, m, C$ |
$1$ | $n, m, C \leq 1000$ |
$2 \sim 3$ | $n, m \leq 100000, C \leq 40$ |
$4 \sim 6$ | $n, m, C \leq 100000$ |
$7 \sim 10$ | $n, m, C \leq 1000000$ |
对于所有数据,$case=3$。