2344. pair-pair

Time Limit : 1000 MS 

Memory Limit : 65536 KB

Pair-Pair

Bobo is tired of all kinds of hard LIS (Longest Increasing Subsequence) problems, so he decides to make himself some easier one.

Bobo has n pairs (a1,b1),(a2,b2),…,(an,bn) where 1≤ai,bi≤m holds for all i. He defines f(i,j) be the length of longest increasing subsequence of sequence {ai,bi,aj,bj}.

It's clear that 1≤f(i,j)≤4. Bobo would like to know g(k) which is the number of pairs (i,j) where f(i,j)=k.

Note that a sequence labeled with {i1,i2,…,ik} is an increasing subsequence of {a1,a2,…,an} only if:

1≤i1<i2<⋯<ik≤nai1<ai2<⋯<aik

Input

The first line contains 2 integers n,m (1≤n≤105,1≤m≤103).

The i-th of the following n lines contains 2 integers ai,bi (1≤ai,bi≤m).

Output

For each set, 4 integers g(1),g(2),g(3),g(4).

Sample Input

2 4

1 2

3 4

2 1

1 1

1 1

Sample Output

0 3 0 1

4 0 0 0