Codeforces Round #416 (Div. 2) has been moved to start on 27.05.2017 09:35 (UTC).
×

No tag edit access

B. Sereja ans Anagrams

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputSereja 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*.

Input

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}).

Output

In the first line print the number of valid *q*s. 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

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/27/2017 03:37:53 (p1).

Desktop version, switch to mobile version.
User lists

Name |
---|