← 返回题目列表

Codeforces · 367/B

B. Sereja 和 Anagrams

中文机器翻译题面 查看原题

Sereja 有两个序列 a 和 b 以及数字 p。序列a由n个整数a1,a2,...,an组成。类似地,序列b由m个整数b1,b2,...,bm组成。像往常一样,塞雷贾研究他拥有的序列。今天他想找到 q (q + (m - 1)·p ≤ n; q ≥ 1) 的个数,使得序列 aq, aq + p, aq + 2p, ..., aq + (m - 1)p 通过重新排列元素可以得到序列 b。

Sereja需要赶去健身房,所以他要求找到所有描述的q位置。

输入

第一行包含三个整数 n、m 和 p (1 ≤ n, m ≤ 2·105, 1 ≤ p ≤ 2·105)。下一行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 109)。下一行包含 m 个整数 b1, b2, ..., bm (1 ≤ bi ≤ 109)。

输出

在第一行中打印有效 q 的数量。在第二行中,按升序打印有效值。

示例

输入 #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