D. Sereja ans Anagrams

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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 mintegers 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 test(s)

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

题意：很容易理解。

分析：离散化->用hash进行线性求解

比赛的时候没有做出来，后来看了别人的思路，然后自己敲了遍代码，贡献了一次超时和两次Runtime Error,不过从中也得到一些收获，题目中a数组和b数组的元素范围为1<=ai,bi<=10^9，此范围比较大，开数组进行hash不好弄，所以第一步就是离散化，离散化之后就是hash进行求解，实践复杂度为线性的，具体看代码实现。

代码实现：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;int n,m,p,total,flag,now;int a[400005],b[400005],c[400005],all[400005],visited[400005];void hebing()//合并成一个数组，全部存在c数组里{    int i,j,x;    total=0;    for(i=1;i<=n;i++)     c[++total]=a[i];    for(i=1;i<=m;i++)     c[++total]=b[i];    sort(c+1,c+1+total);    x=0;    for(i=1;i<=total;i++)//去重     if(i==1||c[i]!=c[i-1])      c[++x]=c[i];    total=x;}int find(int x)//二分查找x处在c数组中的位置{    int l=1,r=total+1,mid;    while(l<=r)    {        mid=(l+r)>>1;        if(c[mid]==x)         return mid;        else if(c[mid]>x)         r=mid-1;        else         l=mid+1;    }}void lisanhua()//对a数组和b数组进行离散化{    int i;    for(i=1;i<=n;i++)     a[i]=find(a[i]);    for(i=1;i<=m;i++)     b[i]=find(b[i]);}void init(){    int i;    flag=0;    memset(all,0,sizeof(all));    for(i=1;i<=m;i++)//哈希处理b数组的情况    {        if(all[b[i]]==0)         flag++;        all[b[i]]++;    }}void add(int x){    visited[x]++;    if(visited[x]==all[x])     now++;}void del(int x){    visited[x]--;    if(visited[x]+1==all[x])     now--;}void solve(){    int res[200005],num=0,i,j,k;    for(i=1;i<=p;i++)//因为相隔为p，所以只需枚举1-p，然后对每一种序列滚动过去    {        if((i+(long long)(m-1)*p)<=n)//因为(m-1)*p已经超过int型，所以要强制转换成long long        {                            //否则就会出现Runtime Error            now=0;            for(j=0;j