描述

序列 A 包含 N 个整数 a1, a2, …, an。
对于每个整数 ai，请统计有多少个整数三元组 (j, k, l) 满足 max{0, i–D} < j <= k <= l < i
并且 aj + ak + al = ai. 其中 D 是一个常数。
依次输出对每个整数 ai(1 <= i <= N) 的答案。

格式

输入格式

第一行，两个整数 N, D。
第二行，N 个整数，依次是 a1, a2, …, an.

输出格式

输出 N 行，每行一个整数，依次表示对每个整数 ai 的答案。

样例1

样例输入1

6 5
4 1 0 -1 3 2

样例输出1

0
0
0
0
2
2

限制

30% 的数据：1 <= N <= 200.
此外有 30% 的数据：1 <= N, Ai <= 2,000.
100% 的数据：1 <= N <= 5,000，1 <= D <= N，|Ai| <= 106.

提示

对 a1 = 4，a2 = 1，a3 = 0，a4 = -1 不存在任何三元组。
对 a5 = 3，满足条件的三元组有 (1, 3, 4)，(2, 2, 2)。
对 a6 = 2，满足条件的三元组有 (2, 2, 3)，(3, 4, 5)。

来源

BJOI 2014 Day 1