**D. Sereja ans Anagrams

D. Sereja ans Anagrams

Sereja has two sequences a and b and number p. Sequence a consists of n integers a1, a2, ..., an. Similarly, sequence b consists of mintegers 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

------------------------------------------------------------EDITORIAL-------------------------------------------

We will divide the sequence on min(n, p) sequences. 1-st, (1 + p)-th, (1 + 2·p)-th, ... element will go to the first sequence, 2-nd,(2 + p)-th, (2 + 2·p)-th... will go to the second sequence and so on. Now you need to find an answer for each of them, considering thatp = 1. This can be solved by a simple method. You can go along the sequence from left to right and count the number of occurrences of each number. If the number of occurrences of each number will match the number of occurrences of the same number in the second sequence, then everything is OK.

FOR COUNTING ME CAN USE MAP FIRST MAP THE 2ND SEQUENCE AND THAN

GO THROUGH EACH SEQUENCE AND  INITIALLY DIFFERENCE IS M AMONG BOTH MAP
NOW INSET   1 ELEMENT AND IF SIZE  OF SLID IS> M REMOVE 1 ELEMENT FROM THE LEFT CORNET IF AFTER THESE 2 OPERATION  DIFFERENCE COUNT =0 THIS IS A VALID SEGMENT .....................
---------------------------------------------------CODE-------------------------------------------------------
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
map<lli,int> ma1,ma2;
lli arr[1000000];
vector<int> idx;
vector<int> tidx;
vector<lli> temp;
int main()
 {
   int n,m,k;
   scanf("%d %d %d",&n,&m,&k);
   for(int i=0;i<n;i++)
   {
     scanf("%lld",&arr[i]);
  }
  for(int i=0;i<m;i++)
  {
    lli a;
    scanf("%lld",&a);
    ma2[a]++;
  }
 
  lli ans=0;
 
  for(int i=0;i<k;i++)
   {
   
       temp.clear();
       tidx.clear();
  
     for(int j=i;j<n;j+=k)
         {
           temp.push_back(arr[j]);
           tidx.push_back(j);
 }

 int sz=temp.size();
 int dif=m;
 ma1.clear();

 for(int j=0;j<m &&  j<sz;j++)
  {
    ma1[temp[j]]++;
     if(ma1[temp[j]]<=ma2[temp[j]]) dif--;
     //else dif++;
  }
  if(dif==0)
  {
   ans++;
   idx.push_back(i);
  }
  for(int j=m;j<sz;j++)
   {
   
   
      ma1[temp[j-m]]--;
      if(ma1[temp[j-m]]<ma2[temp[j-m]]) dif++;
      ma1[temp[j]]++;
      if(ma1[temp[j]]<=ma2[temp[j]]) dif--;
      if(dif==0)
 {
  ans++;
  idx.push_back(tidx[j-m+1]);
 }
   }
   }
  
    cout<<ans<<endl;
    sort(idx.begin(),idx.end());
    for(int i=0;i<ans;i++)
     cout<<idx[i]+1<<" ";
 }