1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
#include "message.h"
#include "poszukiwania.h"
#include <bits/stdc++.h>
using namespace std;
const int md[3]={1000000103,1000000123,1000000181};
const long long H=1000000097;
int le[111],ri[111],l[111],r[111],b[111][3],bp[111][3],c[3],p[3],h[3],z[3];
long long pwn[3];
long long pw(long long a, int b, int md) {
  if (b==0) return 1LL;
  if (b&1) return (pw(a,b-1,md)*a)%md;
  long long x=pw(a,b/2,md);
  return (x*x)%md;
}
int main() {
  int N=NumberOfNodes();
  int M=MyNodeId();
  int A=SignalLength();
  int B=SeqLength();
  int x=A/N,y=A%N;
  for (int i=0; i<N; i++) {
    le[i]=(i==0)?0:ri[i-1];
    ri[i]=le[i]+x+int(i<y);
  }
  for (int j=0; j<3; j++) { p[j]=1; c[j]=0; }
  for (int i=le[M]; i<ri[M]; i++) {
    int cur=SignalAt(i+1);
    for (int j=0; j<3; j++) {
      p[j]=(p[j]*H)%md[j];
      c[j]=(c[j]*H+cur)%md[j];
    }
  }
  for (int i=0; i<N; i++) {
    for (int j=0; j<3; j++) {
      PutInt(i,p[j]);
      PutInt(i,c[j]);
    }
    Send(i);
  }
  for (int i=0; i<N; i++) {
    Receive(i);
    for (int j=0; j<3; j++) {
      int pp=GetInt(i);
      int cc=GetInt(i);
      h[j]=(1LL*h[j]*pp+cc)%md[j];
    }
  }
  x=B/N; y=B%N;
  for (int i=0; i<N; i++) {
    l[i]=(i==0)?0:r[i-1];
    r[i]=l[i]+x+int(i<y);
  }
  for (int j=0; j<3; j++) { p[j]=1; c[j]=0; }
  for (int i=l[M]; i<r[M]; i++) {
    int cur=SeqAt(i+1);
    for (int j=0; j<3; j++) {
      p[j]=(p[j]*H)%md[j];
      c[j]=(c[j]*H+cur)%md[j];
    }
  }
  for (int i=0; i<N; i++) {
    for (int j=0; j<3; j++) {
      PutInt(i,p[j]);
      PutInt(i,c[j]);
    }
    Send(i);
  }
  for (int i=0; i<N; i++) {
    Receive(i);
    for (int j=0; j<3; j++) {
      bp[i][j]=GetInt(i);
      b[i][j]=GetInt(i);
    }
  }
  int res=0;
  for (int j=0; j<3; j++) {
    int i;
    for (i=M; i<N; i++) if (r[i]<l[M]+A) z[j]=(1LL*z[j]*bp[i][j]+b[i][j])%md[j]; else break;
    if (i<N) for (int e=l[i]; e<l[M]+A-1; e++) z[j]=(z[j]*H+SeqAt(e+1))%md[j];
    pwn[j]=pw(H,A-1,md[j]);
  }
  for (int i=l[M]; i<r[M] && i+A<=B; i++) {
    int cur=SeqAt(i+A);
    for (int j=0; j<3; j++) z[j]=(z[j]*H+cur)%md[j];
    {
      int j=0;
      for (; j<3; j++) if (z[j]!=h[j]) break;
      if (j>=3) res++;
    }
    cur=SeqAt(i+1);
    for (int j=0; j<3; j++) z[j]=(z[j]+md[j]-(cur*pwn[j])%md[j])%md[j];
  }
  PutInt(0,res);
  Send(0);
  if (M==0) {
    int sum=0;
    for (int i=0; i<N; i++) {
      Receive(i);
      sum+=GetInt(i);
    }
    cout<<sum<<'\n';
  }
  return 0;
}