Description

The once-in-60-years magic war is about to begin, and the grand mage is preparing to draw magic energy from nearby magic fields.

The grand mage has $m$ magic items, numbered $1, 2, \ldots, m$. Each item has a magic value, denoted $X_i$ for the item with index $i$. Each magic value $X_i$ is a positive integer not exceeding $n$, and multiple items may share the same magic value.

The grand mage believes that a set of four items with indices $a, b, c, d$ forms a magic formation 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 calls these four items the $A$ item, $B$ item, $C$ item, and $D$ item of that magic formation, respectively.

Now, the grand mage wants to know, for each magic item, how many times it appears as the $A$ item in some magic formation, as the $B$ item, as the $C$ item, and as the $D$ item.

Input Format

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

Then follow $m$ lines, each containing one positive integer. The integer on line $i+1$ is $X_i$, the magic value of the item with index $i$.

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

Output Format

Output $m$ lines, each containing $4$ integers. The $i$-th line contains $4$ integers, which are the counts of item $i$ appearing as the $A$, $B$, $C$, and $D$ items, respectively.

It is guaranteed that every number in the standard output does not exceed $10^9$. There must be exactly one space between any two adjacent numbers on the same line.

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

Hint

[Sample Explanation $1$]

There are $5$ magic formations in total, namely:

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

Take item $5$ as an example. It appears once as the $A$ item and $3$ times as the $B$ item. It does not appear as the $C$ or $D$ item. Therefore, the four numbers on that line are $1, 3, 0, 0$.

In addition, if we view the output as an $m$-by-$4$ matrix, then the sum of the $m$ numbers in each column should equal the total number of magic formations. Therefore, if your output does not satisfy this property, it must be incorrect. You can use this property to partially check the correctness of your output.

[Constraints]

Translated by ChatGPT 5