Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

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-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/12/2018 16:20:37 (d2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|