Problem3257--Sereja ans Anagrams

3257: Sereja ans Anagrams

[Creator : ]
Time Limit : 2.000 sec  Memory Limit : 256 MiB

SubmitSolved: 0Submit Num: 0StatisticsShowOff!

Description

time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Sereja has two sequences a and b and number p. Sequence a consists of n integers a1,a2,...,an. Similarly, sequence b consists of m integers b1,b2,...,bm. 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 aq,aq+p,aq+2p,...,aq+(m-1)p by rearranging elements.

Sereja needs to rush to the gym, so he asked to find all the described positions of q.

Input

The first line contains three integers n, m and p (1≤n,m≤2·105,1≤p≤2·105). The next line contains n integers a1, a2, ..., an (1≤ai≤109). The next line contains m integers b1, b2, ..., bm (1≤bi≤109).

Output

In the first line print the number of valid qs. In the second line, print the valid values in the increasing order.

Examples
Input
5 3 1
1 2 3 2 1
1 2 3
Output
2
1 3
Input
6 3 2
1 3 2 2 3 1
1 2 3
Output
2
1 2

Source/Category

 
Submit