Sereja ans Anagrams

题意翻译

### 题目翻译 Sereja 有两个序列 $a$ 和 $b$，还有一个数字 $p$。$a$ 序列为 $a_1,a_2,a_3,\cdots,a_n$，$b$ 序列为 $b_1,b_2,b_3,\cdots,b_n$。 Sereja 像往常一样学习他的序列，今天他想要找到若干个正整数 $q$ 使得 $q+(m-1) \times p \le n$ 并且 $q \ge 1$，同时需要满足的是 $a_q,a_{q+p},a_{q+2 \times p},\cdots,a_{q+(m-1) \times p}$ 和 $b$ 序列一样。 定义这里的序列一样不需要每个位置上的数相同，只需要他们所包含的数值相同。 比如 $1,2,3$ 和 $1,3,2$ 是一样的，但是 $1,3,3$ 和 $1,3,2$ 是不一样的。 ### 输入格式 第一行三个正整数 $n,m,q$。 第二行是 $a$ 序列。 第三行是 $b$ 序列。 ### 输出格式 第一行，表示 $q$ 有多少个数值。 第二行以升序输出 $q$。

题目描述

Sereja has two sequences $ a $ and $ b $ and number $ p $ . Sequence $ a $ consists of $ n $ integers $ a_{1},a_{2},...,a_{n} $ . Similarly, sequence $ b $ consists of $ m $ integers $ b_{1},b_{2},...,b_{m} $ . As usual, Sereja studies the sequences he has. Today he wants to find the number of positions $ q $ $ (q+(m-1)·p<=n; q>=1) $ , such that sequence $ b $ can be obtained from sequence $ a_{q},a_{q+p},a_{q+2p},...,a_{q+(m-1)p} $ by rearranging elements. Sereja needs to rush to the gym, so he asked to find all the described positions of $ q $ .

输入输出格式

输入格式

The first line contains three integers $ n $ , $ m $ and $ p $ $ (1<=n,m<=2·10^{5},1<=p<=2·10^{5}) $ . The next line contains $ n $ integers $ a_{1} $ , $ a_{2} $ , $ ... $ , $ a_{n} $ $ (1<=a_{i}<=10^{9}) $ . The next line contains $ m $ integers $ b_{1} $ , $ b_{2} $ , $ ... $ , $ b_{m} $ $ (1<=b_{i}<=10^{9}) $ .

输出格式

In the first line print the number of valid $ q $ s. In the second line, print the valid values in the increasing order.

输入输出样例

输入样例 #1

5 3 1
1 2 3 2 1
1 2 3

输出样例 #1

2
1 3

输入样例 #2

6 3 2
1 3 2 2 3 1
1 2 3

输出样例 #2

2
1 2