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
122
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (b); i >= (a); i--)
#define SZ(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define st first
#define nd second
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
auto &operator<<(auto &o, pair<auto, auto> p) {
    return o << "(" << p.st << ", " << p.nd << ")";
}
auto operator<<(auto &o, auto x)->decltype(end(x), o) {
    o << "{"; int i=0; for(auto e: x) o << ", " + 2*!i++ << e;
    return o << "}";
}
#define deb(x...) cerr << "[" #x "]: ", [](auto...$) { ((cerr<<$<<"; "),...) << endl; }(x)

const int nax = 6e5 + 5;
int a[nax];
int b[nax];
int tmpa[nax];
int tmpb[nax];
int n, m;
vector<int> divs[nax];

void prep(){
    rep(i, 1, nax - 1){
        for(int j=i;j<nax;j+=i) divs[j].pb(i);
    }
}

const int mod = 1e9 + 7;
int ans[nax + nax];

void add(int id, ll co){
    ans[id] += co % mod;
    ans[id] %= mod;
}

int need[nax];

vector<int> record[nax];

void go(){
    rep(i, 1, n){
        fill(need, need + nax, 0);
        rep(j, 0, n) record[j].clear();
        int cur = 0;
        int last = 0;
        rep(j, i + 1, n){
            int rel = (a[j] > a[j - 1]);
            if(!rel) rel = -1;
            if(rel != last) cur = 1;
            else cur++;
            last = rel;
            for(int d : divs[cur - 1]){
                need[d] += 1;
                record[need[d]].pb(j);
            }
        }

        rep(len, 1, m){
            if(i + len > n) break;
            int ways = m + 1 - len;
            int lastNotDone = i + len;
            int ptr = 1;
            rep(j, 0, SZ(record[len + 1]) - 1){
                int from = i + len;
                if(j > 0) from = record[len + 1][j - 1];
                int to = record[len + 1][j] - 1;
                if(to >= from){
                    add(ptr, 1LL * ways * (to - from + 1));
                }
                lastNotDone = record[len + 1][j];
                ptr += 1;
            }
            if(lastNotDone <= n){
                add(ptr, 1LL * ways * (n - lastNotDone + 1));
            }
        }
    }
}

void solve(){
    prep();
    cin >> n >> m;
    rep(i, 1, n) cin >> a[i];
    rep(i, 1, m) cin >> b[i];
    
    rep(len, 1, min(n, m)){
        int w1 = (n - len + 1);
        int w2 = (m - len + 1);
        add(1, 1LL * w1 * w2);
    }

    go();
    rep(i, 1, n) tmpb[i] = a[i];
    rep(i, 1, m) tmpa[i] = b[i];
    swap(n, m);
    rep(i, 1, n) a[i] = tmpa[i];
    rep(i, 1, m) b[i] = tmpb[i];
    go();
    rep(i, 1, n + m) cout << ans[i - 1] << " ";
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int tt = 1;
    // cin >> tt;
    rep(te, 1, tt) solve();
    return 0;
}