Description

六十年一次的魔法战争就要开始了，大魔法师准备从附近的魔法场中汲取魔法能量。
大魔法师有 m 个魔法物品，编号分别为 1, 2, . . . , m 。每个物品具有一个魔法值，我们用 xi 表示编号为 i 的物品的魔法值。 每个魔法值 xi 是不超过 n 的正整数，可能有多个物品的魔法值相同。
大魔法师认为，当且仅当四个编号为 a, b, c, d 的魔法物品满足 xa  < xb  < xc  < xd  ， xb − xa = 2(xd − xc) ，并且 xb − xa < (xc − xb) ÷ 3 时，这四个魔法物品形成了一个魔法阵，他称这四个魔法物品分别为这个魔法阵的A 物品，B  物品，C  物品，D  物品。
现在，大魔法师想要知道，对于每个魔法物品，作为某个魔法阵的A物品出现的次数，作为B 物品的次数，作为C 物品的次数，和作为D 物品的次数。

每个测试点的详细数据范围表：

Input Format

输入文件的第一行包含两个空格隔开的正整数 n 和 m 。

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

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

Output Format

共输出m行，每行四个整数。第i行的四个整数依次 表示编号为i的物品作为A,B,C,D  物品分别出现的次数。 保证标准输出中的每个数都不会超10^9  。 每行相邻的两个数之间用恰好一个空格隔开。

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

Hint

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