#NOIP2016D. 魔法阵

魔法阵

Description

六十年一次的魔法战争就要开始了,大魔法师准备从附近的魔法场中汲取魔法能 量。

大魔法师有m 个魔法物品,编号分别为 1,2,..., m 。每个物品具有一个魔法值,我 们用x**i 表示编号为 i 的物品的魔法值。每个魔法值x**i 是不超过n 的正整数,可能有多 个物品的魔法值相同。

大魔法师认为,当且仅当四个编号为 a , b , c , d 的魔法物品满足 $x_a < x_b < x_c < x_d , x_b - x_a = 2(x_d - x_c ) ,并且 x_b - x_a < (x_c - x_b ) ÷ 3 $时,这四个魔法物品形成了一个魔法阵, 他称这四个魔法物品分别为这个魔法阵的A 物品,B 物品,C 物品,D 物品。

现在,大魔法师想要知道,对于每个魔法物品,作为某个魔法阵的A 物品出现的 次数,作为B物品的次数,作为C 物品的次数,和作为D 物品的次数。

Format

Input

从文件magi c . in 中读入数据。

输入文件的第一行包含两个空格隔开的正整数 nm

接下来 m 行,每行一个正整数,第 i + 1 行的正整数表示xix_i ,即编号为 i 的物品的 魔法值。

保证$ 1 \le n \le 15000, 1 \le m \le 40000, 1 \le x_i \le n $。每个 xix_i 是分别在合法范围内等概率 随机生成的。

Output

输出到文件magi c . out 中。

共输出 m 行,每行四个整数。 第 i 行的四个整数依次表示编号为 i 的物品作 为A,B,C,D 物品分别出现的次数。

保证标准输出中的每个数都不会超过 10910^9

每行相邻的两个数之间用恰好一个空格隔开。

Samples

30  8
1
24
7
28
5
29
26
24
4  0  0  0
0  0  1  0
0  2  0  0
0  0  1  1
1  3  0  0
0  0  0  2
0  0  2  2
0  0  1  0
15  15
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
5  0  0  0
4  0  0  0
3  5  0  0
2  4  0  0
1  3  0  0
0  2  0  0
0  1  0  0
0  0  0  0
0  0  0  0
0  0  1  0
0  0  2  1
0  0  3  2
0  0  4  3
0  0  5  4
0  0  0  5

Limitation

【样例1说明】

共有 5 个魔法阵,分别为:

物品 1. 3. 7. 6 ,其魔法值分别为 1. 7. 26. 29 :

物品 1. 5. 2. 7 ,其魔法值分别为 1. 5. 24. 26 :

物品 1. 5. 7. 4 ,其魔法值分别为 1. 5. 26. 28 :

物品 1. 5. 8. 7 ,其魔法值分别为 1. 5. 24. 26 :

物品5. 3. 4. 6 ,其魔法值分别为 5. 7. 28. 29 。

以物品 5 为例,它作为A 物品出现了 1 次,作为B物品出现了 3 次,没有作为C 物 品或者D 物品出现,所以这一行输出的四个数依次为 1. 3. 0. 0 。

此外,如果我们将输出看作一个 m 行 4 列的矩阵,那么每一列上的 m 个数之和都 应等于魔法阵的总数。所以,如果你的输出不满足这个性质,那么这个输出一定不正 确。你可以通过这个性质在一定程度上检查你的输出的正确性。 【子任务】

每个测试点的详细数据范围见下表。

测试点编号 n m
1 = 10 = 12
2 = 15 = 18
3 = 20 = 25
4 = 30 = 35
5 = 40 = 50
6 = 50 = 70
7 = 65 = 100
8 = 80 = 125
9 = 100 = 150
10 = 125 = 200
11 = 150 = 250
12 = 200 = 350
13 = 250 = 500
14 = 350 = 700
15 = 500 = 1000
16 = 700 = 2000
17 = 1000 = 5000
18 = 2000 = 10000
19 = 5000 = 20000
20 = 15000 = 40000