2016 T4 魔法阵

主知识点：枚举。交叉标签：枚举、前缀和、计数。
暴力标注：不属于重点 DP 退路题。
OJ 使用标准输入与标准输出。原比赛文件名为 magic.in / magic.out；下方如保留原文件约定，以本句的 OJ 约定为准。
时限 1 秒；内存 512 MiB；测试点 20；总分 100。
数据来源：官网数据；与公开存档逐文件一致。

题目描述

有 $m$ 个带编号的物品，第 $i$ 个物品的魔法值为 $X_i$，其中 $1\le X_i\le n$，不同物品的值可以相同。

编号四元组 $(a,b,c,d)$ 构成魔法阵，当且仅当：

$$X_a<X_b<X_c<X_d,\qquad X_b-X_a=2(X_d-X_c),\qquad 3(X_b-X_a)<X_c-X_b.$$

对每件物品分别统计它处于四元组第 1、第 2、第 3、第 4 个位置的次数。物品按编号区分。

输入格式

第一行包含两个空格隔开的正整数 $n,m$。

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

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

输出格式

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

保证标准输出中的每个数都不会超过 $10^9$。每行相邻的两个数之间用恰好一个空格隔开。

样例

样例 1

输入：

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

样例 2

输入：

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

数据范围与特殊性质

$1\le n\le15000$，$1\le m\le40000$，$1\le X_i\le n$。每个 $X_i$ 在对应范围独立均匀随机生成。保证输出中每个数不超过 $10^9$。

测试点	$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

附加样例

本题的公开样例整理在对应的“样例”ZIP 中。样例不计入评测测试点；题面中的样例也已保留。

来源与整理说明

题目原作者/发布者：中国计算机学会 CCF / NOI。题意经过改写，保留公式、输入输出、样例及约束；知识点和暴力标注为本次整理补充。

• 题面及约束校对来源：洛谷 CCF_NOI 题目 P2119
• 赛事：NOIP 普及组复赛（CSP-J 前身） 2016。
• 详细数据来源、版本和哈希见总包 来源与校验/manifest.json。