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

Input

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

Output

2
3
3
4
2