Problem Background

NOIP2016 Junior Group T4

Problem Description

The magic war, which occurs once every sixty years, is about to begin. The Great Mage plans to extract magical energy from nearby magical fields.

The Great Mage has $m$ magical items, numbered from $1$ to $m$. Each item has a magical value, denoted as $X_i$ for the item with the number $i$. Each magical value $X_i$ is a positive integer not exceeding $n$, and multiple items may have the same magical value.

The Great Mage believes that four items with numbers $a, b, c, d$ form a magic array if and only if they satisfy $X_a < X_b < X_c < X_d$, $X_b - X_a = 2(X_d - X_c)$, and $X_b - X_a < (X_c - X_b) / 3$. He refers to these four items as the $A$ item, $B$ item, $C$ item, and $D$ item of the magic array, respectively.

Now, the Great Mage wants to know, for each magical item, the number of times it appears as the $A$ item, $B$ item, $C$ item, and $D$ item in a magic array.

Input Format

The first line contains two positive integers $n$ and $m$ separated by a space.

The next $m$ lines each contain a positive integer. The $i+1$-th line contains the integer $X_i$, which represents the magical value of the item numbered $i$.

It is guaranteed that $1 \leq n \leq 15000$, $1 \leq m \leq 40000$, and $1 \leq X_i \leq n$. Each $X_i$ is generated randomly within the valid range.

Output Format

The output consists of $m$ lines, each containing $4$ integers. The $i$-th line's four integers represent the number of times the item numbered $i$ appears as the $A$, $B$, $C$, and $D$ items, respectively.

It is guaranteed that each number in the standard output does not exceed $10^9$. Each pair of adjacent numbers in a line is separated by exactly one space.

Sample Input and Output

Input Sample #1

30 8
1
24
7
28
5
29
26
24

Output Sample #1

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

Input Sample #2

15 15
1 
2 
3 
4 
5
6 
7 
8 
9
10
11
12
13
14
15

Output Sample #2

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

Notes

Sample Explanation #1

There are $5$ magic arrays, as follows:

• Items $1, 3, 7, 6$ with magical values $1, 7, 26, 29$;
• Items $1, 5, 2, 7$ with magical values $1, 5, 24, 26$;
• Items $1, 5, 7, 4$ with magical values $1, 5, 26, 28$;
• Items $1, 5, 8, 7$ with magical values $1, 5, 24, 26$;
• Items $5, 3, 4, 6$ with magical values $5, 7, 28, 29$.

Taking item $5$ as an example, it appears as the $A$ item once, as the $B$ item three times, and does not appear as the $C$ or $D$ item, so the output for this line is $1, 3, 0, 0$.

Additionally, if we consider the output as an $m$ by $4$ matrix, the sum of each column should equal the total number of magic arrays. Therefore, if your output does not satisfy this property, it is definitely incorrect. You can use this property to check the correctness of your output to some extent.

Data Scale

见题面 Input 部分

见题面 Output 部分