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
#include <cstdio>
#include <algorithm>
#include <vector>

const int INF = 0x3f3f3f3f;

struct item {
	int l, r, d;
};

bool operator<(item a, item b) {
	return a.l < b.l;
}

const int N = 100000;
const int K = 12;
int n, k, a[2][N], delta[N * 4], init[N * 2];
long long ans[K];
std::vector<item> vec;

struct engine {
	std::pair<int, int> a[K];
	engine() {
		for (int i = 0; i < K; ++i) a[i] = std::make_pair(INF, 0);
	}
} t[N * 4];

engine operator+(engine a, engine b) {
	engine res;
	for (int i = 0, j = 0, ind = 0; ind <= k; ++ind) {
		if (a.a[i].first <= b.a[j].first) {
			res.a[ind] = a.a[i];
			if (a.a[i].first == b.a[j].first) {
				res.a[ind].second += b.a[j].second;
				++j;
			}
			++i;
		} else {
			res.a[ind] = b.a[j];
			++j;
		}
	}
	return res;
}

void build(int v = 0, int tl = 0, int tr = 2 * n) {
	if (tr - tl == 1) t[v].a[0] = std::make_pair(init[tl], 1);
	else {
		int m = tl + tr >> 1;
		build(v + 1, tl, m);
		build(v + (tr - tl & ~1), m, tr);
		t[v] = t[v + 1] + t[v + (tr - tl & ~1)];
	}
}

void apply(int v, int d) {
	for (int i = 0; i < K; ++i) t[v].a[i].first += d;
}

void inc(int l, int r, int d, int v = 0, int tl = 0, int tr = n * 2) {
	if (!(tl >= r || tr <= l)) {
		if (tl >= l && tr <= r) {
			delta[v] += d;
			apply(v, d);
		} else {
			int m = tl + tr >> 1;
			inc(l, r, d, v + 1, tl, m);
			inc(l, r, d, v + (tr - tl & ~1), m, tr);
			t[v] = t[v + 1] + t[v + (tr - tl & ~1)];
			apply(v, delta[v]);
		}
	}
}

void add2(int x, int y) {
	vec.push_back({std::min(x, y), std::max(x, y), -1});
	init[std::max(x, y)] -= 1;
}

void add4(std::vector<int> v) {
	std::sort(v.begin(), v.end());
	vec.push_back({v.front(), v.back(), 1});
	init[v.back()] += 1;
}

int main() {
	scanf("%d%d", &n, &k);
	for (int i = 0; i < 2; ++i) for (int j = 0; j < n; ++j) {
		scanf("%d", a[i] + j);
		--a[i][j];
	}
	for (int i = 0; i < n; ++i) {
		add2(a[0][i], a[1][i]);
		add2(a[0][i], a[0][(i + 1) % n]);
		add2(a[1][i], a[1][(i + 1) % n]);
		add4({a[0][i], a[1][i], a[0][(i + 1) % n], a[1][(i + 1) % n]});
	}
	for (int i = 0; i < 2 * n; ++i) {
		++init[i];
		init[i + 1] += init[i];
	}
	build();
	std::sort(vec.begin(), vec.end());
	for (int i = 0, j = 0; i < 2 * n; ++i) {
		for (int j = 0; j < K; ++j) if (t[0].a[j].first <= k) ans[t[0].a[j].first] += t[0].a[j].second;
		inc(i, 2 * n, -1);
		for (; j < (int)vec.size() && vec[j].l == i; ++j) inc(vec[j].r, 2 * n, -vec[j].d);
	}
	ans[1] += ans[0] - (long long)n * (2 * n - 1);
	for (int i = 1; i <= k; ++i) printf("%lld ", ans[i]);
	printf("\n");
	return 0;
}