LIS of Pairs

You have $n$ pairs $(a_1,b_1),(a_2,b_2),\dots ,(a_n,b_n)$ of integers, where $1\le a_i,b_i\le m$ holds for all $i$.

Let's define $f(i,j)$ as the length of the longest strictly increasing subsequence of the sequence $\{a_i,b_i,a_j,b_j\}$.

It's clear that $1\le f(i,j)\le 4$.

For every $k$ from $1$ to $4$, find the number of ordered pairs $(i,j)$ with $1\le i,j\le n$, for which $f(i,j)=k$.

Note that a sequence labeled with $\{i_1,i_2,\dots ,i_k\}$ is an increasing subsequence of $\{a_1,a_2,\dots ,a_n\}$ only if:

• $1\le i_1<i_2<\cdots <i_k\le n$

• $a_{i_1}<a_{i_2}<\cdots <a_{i_k}$

Input

The first line of the input contains $2$ integers $n,m$ ($1\le n\le 10^5,1\le m\le 10^3$).

The $i$-th of the following $n$ lines contains $2$ integers $a_i,b_i$ ($1\le a_i,b_i\le m$).

Output

Print $4$ integers. The $k$-th of them should be equal to the number of ordered pairs $(i,j)$ with $1\le i,j\le n$, for which $f(i,j)=k$.

Examples

Note

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$.