You have n pairs (a1,b1),(a2,b2),…,(an,bn) of integers, where 1≤ai,bi≤m holds for all i.
Let's define f(i,j) as the length of the longest strictly increasing subsequence of the sequence {ai,bi,aj,bj}.
It's clear that 1≤f(i,j)≤4.
For every k from 1 to 4, find the number of ordered pairs (i,j) with 1≤i,j≤n, for which 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≤n
ai1<ai2<⋯<aik
The first line of the input 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).
Print 4 integers. The k-th of them should be equal to the number of ordered pairs (i,j) with 1≤i,j≤n, for which f(i,j)=k.
In the first sample:
f(1,1)=LIS(1,2,1,2)=2.
f(1,2)=LIS(1,2,3,4)=4.
f(2,1)=LIS(3,4,1,2)=2.
f(2,2)=LIS(3,4,3,4)=2.
In the second sample, all numbers are equal, so we wouldn't be able to choose any increasing subsequence of length at least 2.