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
123
124
125
126
127
128
129
130
131
132
133
134
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll N = 6e5 + 5, Mod = 1e9 + 7;

inline ll sqr(ll x){
	return x * x % Mod;
}

inline void upd(ll &x, ll dx){
	x = (x + dx) % Mod;
}

class bit{
private:
ll n, t[N];

public:

inline void init(ll n0){
	n = n0;
	for(ll i = 1 ; i <= n ; i ++) t[i] = 0;
}

inline ll lowbit(ll x){
	return x & -x;
}

inline void modify(ll p, ll x){
	x = (x * (Mod + 1) / 2) % Mod;
	while(p <= n){
		upd(t[p], x);
		p = p + lowbit(p);
	}
}

inline ll qry(ll p){
	ll ret = 0;
	while(p > 0){
		upd(ret, t[p]);
		p = p - lowbit(p);
	}
	return ret;
}

inline ll query(ll l, ll r){
	return (qry(r) - qry(l - 1) + Mod) % Mod;
}

} f, g, h;

ll n = 0, m = 0, k = 0, a[N] = {}, b[N] = {}, pre[N] = {}, suf[N] = {}, ans[N] = {};
vector<ll> pos[N] = {};

inline void init(){
	memset(pre, 0, sizeof(pre)), memset(suf, 0, sizeof(suf));
	k = 0, memset(b, 0, sizeof(b));
	for(ll i = 0 ; i < N ; i ++) pos[i].clear();
}

inline void solve(){
	for(ll i = 2, p = 0, x = 1 ; i <= n ; i ++){
		if(a[i] < a[i - 1]){
			if(p == 1){
				b[++ k] = x;
				p = -1, x = 1;
			}
			else p = -1, x ++;
		}
		else{
			if(p == -1){
				b[++ k] = x;
				p = 1, x = 1;
			}
			else p = 1, x ++;
		}
		if(i == n) b[++ k] = x;
	}
	for(ll i = 1 ; i <= k ; i ++){
		for(ll x = 3 ; x <= b[i] ; x ++) upd(suf[x], (b[i] - x + 1));
		for(ll x = 1 ; x <= b[i] ; x ++) pos[x].push_back(i);
		pre[i] = pre[i - 1] + b[i];
	}
	for(ll x = n ; x >= 1 ; x --) upd(suf[x], suf[x + 1]);
	for(ll x = 1 ; x <= n ; x ++) for(ll d = 1 ; (d + 1) * x <= n && d <= m ; d ++) upd(ans[x], suf[(d + 1) * x + 2] * (m - d + 1));
	for(ll x = 1 ; x <= n ; x ++){
		f.init(n / x + 5), g.init(n / x + 5), h.init(n / x + 5);
		ll cur = 1, j = 0;
		for(ll i : pos[x]){
			if(j != i - 1){
				ll val = pre[i - 1] - pre[j], l = max(cur - m, 1ll), r = cur - 1, z = cur - 1;
				upd(ans[x], (((2 * m + 1) * z + Mod - sqr(z)) % Mod * f.query(l, r) + (2 * z + Mod - 2 * m - 1) % Mod * g.query(l, r) + (Mod - 1) * h.query(l, r)) % Mod * val);
				if(l > 1) upd(ans[x], ((m + 1) * m) % Mod * f.query(1, l - 1) % Mod * val);
				f.modify(cur, val), g.modify(cur, val * cur % Mod), h.modify(cur, val * sqr(cur) % Mod);
			}
			if(i > 1) for(ll s = 1 ; s <= b[i] ; ){
				ll t = min(s + x - 1, b[i]), val = t - s + 1; if(s > 1) cur ++;
				ll l = max(cur - m, 1ll), r = cur - 1, z = cur - 1;
				upd(ans[x], (((2 * m + 1) * z + Mod - sqr(z)) % Mod * f.query(l, r) + (2 * z + Mod - 2 * m - 1) % Mod * g.query(l, r) + (Mod - 1) * h.query(l, r)) % Mod * val);
				if(l > 1) upd(ans[x], ((m + 1) * m) % Mod * f.query(1, l - 1) % Mod * val);
				s = t + 1;
			}
			else cur += (b[i] - 1) / x;
			ll las = cur;
			for(ll s = 1 ; s <= b[i] ;){
				ll t = min((s == 1) ? (x + 1) : (s + x - 1), b[i]), val = t - s + 1; if(s > 1) cur --;
				f.modify(cur, val), g.modify(cur, val * cur % Mod), h.modify(cur, val * sqr(cur) % Mod);
				s = t + 1;
			}
			cur = las, j = i;
		}
		if(j != k){
			ll val = pre[k] - pre[j], l = max(cur - m, 1ll), r = cur - 1, z = cur - 1;
			upd(ans[x], (((2 * m + 1) * z + Mod - sqr(z)) % Mod * f.query(l, r) + (2 * z + Mod - 2 * m - 1) % Mod * g.query(l, r) + (Mod - 1) * h.query(l, r)) % Mod * val);
			if(l > 1) upd(ans[x], ((m + 1) * m) % Mod * f.query(1, l - 1) % Mod * val);
		}
	}
}

int main(){
	scanf("%lld %lld", &n, &m);
	for(ll i = 1 ; i <= n ; i ++) scanf("%lld", &a[i]);
	init(), solve();
	swap(n, m);
	for(ll i = 1 ; i <= n ; i ++) scanf("%lld", &a[i]);
	init(), solve();
	ans[0] = ((n * (n + 1) / 2) % Mod) * ((m * (m + 1) / 2) % Mod) % Mod;
	for(ll i = 0 ; i < n + m - 1 ; i ++) ans[i] = (ans[i] + Mod - ans[i + 1]) % Mod;
	printf("0 ");
	for(ll i = 0 ; i < n + m - 1 ; i ++) printf("%lld ", ans[i]);
	return 0;
}