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
#include <bits/stdc++.h>

using namespace std;

const int N = 300'000 + 7;

int n, m, a[N], b[N];
long long ans[N + N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= m; i++)
		cin >> b[i];
	
	// przedzialy o tej samej dlugosc
	for (int i = 1; i <= min(n, m); i++) {
		// cerr << "tyle samo o dlg: " << i << " => " << (n - i + 1) * (m - i + 1) << '\n';
		ans[2] += (n - i + 1) * (m - i + 1);
	}
	
	for (int rep : {0, 1}) {

		// cerr << "REP: " << rep << '\n';

		// bierzemy z a przedzial dluzszy i dokladamy krotszy od b
		for (int i = 1; i <= n; i++) {
			// cerr << "start: " << i << '\n';

			int inc = 1;
			int dec = 1;

			vector<int> all;
			vector<int> ile(n + m); // chemy uzyskac wynik x -> ile potrzeba nam do tego elementow z b

			auto add = [&](int x) {
				if (x <= 2)
					return;

				// cerr << "adding: " << x << '\n';

				for (int y = 2; y <= x; y++) {
					ile[y] += (x - 2) / (y - 1);
				}
			};

			auto del = [&](int x) {
				if (x <= 2)
					return;

				// cerr << "deleting: " << x << '\n';

				for (int y = 2; y <= x; y++) {
					ile[y] -= (x - 2) / (y - 1);
				}
			};
			
			for (int j = i + 1; j <= n; j++) {

				if (a[j - 1] < a[j]) {
					add(dec);
					dec = 1;
					inc++;
				}
				else {
					add(inc);
					inc = 1;
					dec++;
				}

				// cerr << "end: " << j << ' ' << inc << ' ' << dec << ' ' << " | " << a[j - 1] << " vs " << a[j] << '\n';
				add(inc);
				add(dec);
				
				int big = min(m, j - i); // najwieksza legalna dlugosc przedzialu z b

				for (int k = 2; k <= n; k++) {
					while (big >= ile[k] && big >= 1) {
						// cerr << "(" << i << "," << j << ") " << rep << " => " << k << ' ' << big << '\n';

						ans[k] += m - big + 1;
						big--;
					}
				}

				del(inc);
				del(dec);
			}
		}

		swap(n, m);
		for (int i = 1; i <= max(n, m); i++)
			swap(a[i], b[i]);
	}

	for (int i = 1; i <= n + m; i++)
		cout << ans[i] % int(1e9 + 7) << ' ';
	cout << '\n';

	return 0;
}