You have $n$ pairs $(a_1, b_1), (a_2, b_2), \dots, (a_n, b_n)$ of integers, where $1 \leq a_i, b_i \leq 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 \leq f(i, j) \leq 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: \begin{itemize} \item $1 \leq i_1 < i_2 < \dots < i_k \leq n$ \item $a_{i_1} < a_{i_2} < \dots < a_{i_k}$ \end{itemize} \InputFile The first line of the input contains $2$ integers $n, m$ ($1 \leq n \leq 10^5, 1 \leq m \leq 10^3$). The $i$-th of the following $n$ lines contains $2$ integers $a_i, b_i$ ($1 \leq a_i, b_i \leq m$). \OutputFile 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$. \Note In the first sample: \begin{itemize} \item $f(1, 1) = LIS(1, 2, 1, 2) = 2$. \item $f(1, 2) = LIS(1, 2, 3, 4) = 4$. \item $f(2, 1) = LIS(3, 4, 1, 2) = 2$. \item $f(2, 2) = LIS(3, 4, 3, 4) = 2$. \end{itemize} In the second sample, all numbers are equal, so we wouldn't be able to choose any increasing subsequence of length at least $2$.