logo AlgoBeat OnlineJudge
登录 注册

#102372. [BZOJ 2372] music

内存限制:128 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

最近 A、B 两国发生了一场战争。dick,作为 A 国的军事总指挥,最近非常头痛于己方的情报问题。因为 B 国最近雇佣了 Easy 这一位密码专家来给他们的所有通讯加密。

Easy 非常喜欢唱歌,于是他决定将所有的信号都变成旋律储存起来,比如说 11556654433221 就可能是一段加过密的音符,我们用一个等长度的序列来表示它,就变成了 。为了增加密码的保密性,他把加密的乐谱又调整了一下,把某些音调改变了,将原序列 变成 ,有 ,且对于 、对 、对 。那么 1122155775 就可能代表了同一段音符。

最近,dick 截获了一段信号,这段信号中可能包含了某些重要信息。根据以往的经验,dick 已经知道了某些旋律所代表的意义。于是 dick 想知道,对于一段已知的旋律,能不能判断它是否在这段截获的旋律中出现?如果出现了,能否找出它出现的次数及位置呢?

「任务」判断给定旋律在截获旋律中出现的次数及位置。

输入格式

本题只有一组数据。

第一行三个正整数 是截获旋律的长度, 是已知旋律的长度,所有的旋律都是 )的正整数。

接下来 行每行一个整数描述截获旋律

接下来 行每行一个整数描述已知旋律

输出格式

第一行一个整数 表示出现的次数。

然后 行,按照从小到大给出出现时的起始位置 (即有 等价于 )。

样例

样例输入 #1

9 6 10
5
6
2
10
10
7
3
2
9
1
4
4
3
2
1

样例输出 #1

1
3

数据范围与提示

对于 的数据,有