NC52816. 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%2C%20(a_2%2C%20b_2)%2C%20%5Cdots%2C%20(a_n%2C%20b_n))
where
holds for all i.
He defines f(i, j) be the length of longest increasing subsequence of sequence
.
It's clear that%20%5Cleq%204)
.
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
is an increasing subsequence of 
only if:
*
*
so he decides to make himself some easier one.
Bobo has n pairs
where
He defines f(i, j) be the length of longest increasing subsequence of sequence
It's clear that
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
*
*
输入描述
The input contains at most 30 sets. For each set:
The first line contains 2 integers n, m ().
The i-th of the following n lines contains 2 integers(
输出描述
For each set, 4 integers g(1), g(2), g(3), g(4).
示例1
输入:
2 4 1 2 3 4
输出:
0 3 0 1
示例2
输入:
2 1 1 1 1 1
输出:
4 0 0 0