Coders Collaborate

In MonTech, there are $M$ collaborative projects, each uniquely identified from 1 to $M$. Today, $N$ coders assemble, numbered from 1 to $N$. Due to the multitude of projects, each coder will only contribute to a specific range of projects.

The $i$-th coder will contribute to projects numbered $a_i$-th, $(a_i + 1)$-th, ..., $b_i$-th project.

You are given a task. For each coder, what is the number of other coders they are collaborating with?

Note: Two coders are collaborating if and only if, they contribute to one or more projects with the same id.

Input

The first line contains two integers, $N$ and $M$ – the number of coders and projects respectively.

The next $N$ lines contain two integers each $a_i$, $b_i$ – the numbers of the projects that the $i$-th coder is contributing to.

Output

$N$ lines, where the $i$-th line contains the number of other coders that are collaboriting with the $i$-th coder.

Constraints

• $1 \le N \le 2\times10^5$
• $1 \le M \le 10^9$
• $1 \le a_i \le b_i \le M$

Example 1

5 5
4 5
1 3
2 4
1 5
1 1

2
3
3
4
2