CodeForces - 367B Sereja ans Anagrams （map）

Submit Status

Description

Sereja has two sequences a and b and number p. Sequence a consists of n integers a₁, a₂, ..., a_n. Similarly, sequence bconsists 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.

Sample Input

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<map>
#define INF 0x3f3f3f3f
#define ull unsigned long long
#define ll long long
#define IN __int64
#define N 200010
#define M 1000000007
using namespace std;
int a[N];int ans[N];
int n,m,p;
map<int,int>A,B;
void ins(int x,int t)
{
	B[x]+=t;
	if(!B[x])
		B.erase(x);
}
int main()
{
	int x,i,j,k;
	scanf("%d%d%d",&n,&m,&p);
	if(1ll*(m-1)*p+1>n)
		printf("0\n");
	else
	{
		for(i=1;i<=n;i++)
			scanf("%d",&a[i]);
		for(i=1;i<=m;i++)
		{
			scanf("%d",&x);
			A[x]++;
		}
		int kk=0;
		for(i=1;i<=p;i++)
		{
			B.clear();
			for(j=i;j<=n;j+=p)
			{
				ins(a[j],1);
				k=j-m*p;
				if(k>0)
					ins(a[k],-1);
				k=j-(m-1)*p;
				if(k>0&&B==A)
					ans[++kk]=k;
			}
		}
		sort(ans+1,ans+kk+1);
		printf("%d\n",kk);
		for(i=1;i<=kk;i++)
			printf("%d ",ans[i]);
	}
	return 0;	
}