Sereja ans Anagrams

Sereja has two sequences a and b and number p. Sequence a consists of n integers a ₁, a ₂, …, a _n. Similarly, sequence b consists of m integers b ₁, b ₂, …, 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⁵, 1 ≤ p ≤ 2·10⁵). The next line contains n integers a ₁, a ₂, …, a _n (1 ≤ a _i ≤ 10⁹). The next line contains m integers b ₁, b ₂, …, b _m (1 ≤ b _i ≤ 10⁹).

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

Solution:

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <set>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <memory.h>
#include <string>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <ctime>
#include <cassert>

using namespace std;

const int N = 1000010;

int cnt[N], zero;

void add(int x, int v) {
if (cnt[x] == 0) zero--;
cnt[x] += v;
if (cnt[x] == 0) zero++;
}

int a[N], b[N], c[N];
vector <int> ans;
vector < pair <int, int> > e;

int main() {
int n, m, p;
scanf("%d %d %d", &n, &m, &p);
for (int i = 0; i < n; i++) scanf("%d", a + i);
  for (int i = 0; i < m; i++) scanf("%d", b + i);
  e.clear();
  for (int i = 0; i < n; i++) e.push_back(make_pair(a[i], i));
  for (int i = 0; i < m; i++) e.push_back(make_pair(b[i], ~i));
  sort(e.begin(), e.end());
  int t = 0;
  for (int i = 0; i < n + m; i++) {
    if (e[i].second >= 0) {
a[e[i].second] = t;
} else {
b[~e[i].second] = t;
}
if (i + 1 < n + m && e[i].first != e[i + 1].first) {
      t++;
    }
  }
  for (int i = 0; i < t; i++) cnt[i] = 0;
  zero = t;
  for (int i = 0; i < m; i++) add(b[i], 1);
  ans.clear();
  for (int r = 0; r < p; r++) {
    int k = 0;
    for (int i = r; i < n; i += p) c[k++] = a[i];
    if (k < m) {
      continue;
    }
    for (int i = 0; i < m - 1; i++) add(c[i], -1);
    for (int i = m - 1; i < k; i++) {
      add(c[i], -1);
      if (zero == t) {
        ans.push_back((i - (m - 1)) * p + r);
      }
      add(c[i - (m - 1)], 1);
    }
    for (int i = k - (m - 1); i < k; i++) add(c[i], 1);
  }
  sort(ans.begin(), ans.end());
  int sz = ans.size();
  printf("%d\n", sz);
  for (int i = 0; i < sz - 1; i++) printf("%d ", ans[i] + 1);
  if (sz > 0) printf("%d", ans[sz - 1] + 1);
printf("\n");
return 0;
}