Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

D2. Predator or Prey (Hard Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the hard version of the problem. The only difference between the easy and hard versions is the constraint on $$$n$$$. Solutions that pass under the time limit for the easy version may not pass the hard version.

Sritan has recently been investigating the predatory relationships of the TJ ecosystem. He has discovered that the $$$i$$$-th animal can be given a predator factor of $$$p_i$$$, which is a positive integer.

He learns that animals will prey on other animals based on their relative predator factors. An animal $$$i$$$ will prey on animal $$$j$$$ if the difference between $$$p_i$$$ and $$$p_j$$$ is at least $$$a$$$. However, if this difference is $$$b$$$ or more, animal $$$i$$$ considers the animal $$$j$$$ to be too weak and will not eat it.

There are $$$n$$$ animals in the TJ ecosystem. For each animal, find the number of predators and prey that it has.

Input

The first line of the input contains three integers $$$n$$$, $$$a$$$, $$$b$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq a \lt b \leq 10^9$$$).

The second line contains the $$$n$$$ integers $$$p_1 \dots p_n$$$ ($$$1 \leq p_i \leq 10^9$$$) representing the animals' predator factors.

Output

Print $$$n$$$ lines. On the $$$i$$$-th line, print $$$2$$$ integers corresponding to the number of predators and the number of prey that animal $$$i$$$ has.

Example
Input
5 3 7
8 6 5 14 12
Output
2 1
1 0
1 0
0 1
0 2
Note

In the sample test case, animal $$$1$$$ will have $$$2$$$ predators (animals $$$4$$$ and $$$5$$$) and $$$1$$$ prey (animal $$$3$$$). Animal $$$4$$$ has only one prey (animal $$$1$$$) since animals $$$2$$$ and $$$3$$$ are too weak for it to eat.