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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<cstdio>
#include<algorithm>
#include<vector>

#define S 600007

using namespace std;
typedef long long ll;
ll mod = 1000000007;

int A[S];
int B[S];

int suf(int x, int y){
    if(x % y == 0)
        return x/y;
    return x/y+1;
}

ll pref[S];
ll ans[S];

int needed[S];

int f(int aim, int len){
    return suf(len-1, aim-1) - 1;
}

void add(int n, int len){
    for(int aim = 2; aim <= n; aim++){
        needed[aim] += f(aim, len);
    }
}

void rm(int n, int len){
    for(int aim = 2; aim <= n; aim++){
        needed[aim] -= f(aim, len);
    }
}

void solve(int n, int m){
    for(int i = 0; i < S; i++){
        pref[i] = 0;
    }
    for(int i = 1; i <= m; i++){
        pref[i] = pref[i-1] + (m-i+1);
    }
    //zakladamy, ze pierwszy ciag jest nie krotszy najpierw
    for(int i = 1; i <= n; i++){
        vector<int> lens{2}; 
        add(n,2);
        for(int j = i+1; j <= n; j++){
            if(j != i+1){
                if((A[j-2] < A[j-1] && A[j-1] < A[j]) || (A[j-2] > A[j-1] && A[j-1] > A[j])){
                    rm(n,lens.back());
                    lens.back()++;
                    add(n,lens.back());
                }else{
                    lens.push_back(2);
                    add(n,lens.back());
                }
            }

            //calc something
            int lastt = min((j-i+2), m+1);
            for(int aim = 2; aim <= n; aim++){
                //how to get aim equal to something
                int p = needed[aim];
                //so we need arrays of size (p, lastt-1)
                if(p == 0)
                    p = 1;
                if(p < lastt){
                    // printf("%d %d %d %lld*\n",i,j,aim,pref[lastt-1] - pref[p-1]);
                    ll x = pref[lastt-1] - pref[p-1];
                    ans[aim] += x;
                    lastt = p;
                }
            }
        }
        for(int aim = 2; aim <= n; aim++){
            needed[aim] = 0;
        }
    }
}

int main(void){
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i = 1; i <= n; i++){
        scanf("%d",&A[i]);
    }
    for(int i = 1; i <= m; i++){
        scanf("%d", &B[i]);
    }

    solve(n,m);

    swap(n,m);
    for(int i = 1; i <= max(n,m); i++){
        swap(A[i], B[i]);
    }


    solve(n,m);

    
    ans[2] += (ll)n * (ll)m;
    for(int i = min(n,m); i >= 1; i--){
        ans[2] -= (ll)(n-i) * (ll)(m-i);
    }
    for(int i = 1; i <= n+m; i++){
        ans[i] %= mod;
        if(ans[i] < 0)
            ans[i] += mod;
        printf("%lld ",ans[i]);
    }
    printf("\n");


    return 0;
}