This page is still under construction.

Parts of this page are still being built. What you see may change.

Blankets

Time limit1sMemory limit128 MB

Summary
Compute the average pairwise overlap area of n identical axis-aligned rectangles from their corner positions.
Level

Medium7 of 10

Topics
Segment tree, Sorting, Geometry, Math
Solved
No attempts yet

Problem

This summer the citizens of Byteburg are streaming down to the city beach on Byteotian Lake to sunbathe. Everyone who comes brings a blanket made by Byteasar & Son, the label everybody wants this season. The blankets differ only in their patterns, all of them measure a×ba \times b, and everyone spreads a blanket so that its longer side is perpendicular to the lake.

Professor Byteoni is one of this year's sunbathers. After a few days on the beach he noticed that every person spreads the blanket on one favourite spot, always the same one. People arrive and leave at different hours, yet the professor has never heard of anyone taking over somebody else's spot. He decided to study the phenomenon himself.

He set up a coordinate system on the beach and wrote down, for each of the nn citizens, the spot where that person always spreads the blanket. The OX axis is parallel to the sides of length aa and the OY axis to the sides of length bb, so citizen ii covers the rectangle [xi,xi+a]×[yi,yi+b][x_i, x_i + a] \times [y_i, y_i + b] whose lower left corner is (xi,yi)(x_i, y_i).

The professor first wanted the overlap area of every pair of blankets. Then he realised that the average of those values is all his research needs. Compute the expected overlap area of the blankets of two different citizens picked at random, where each of the (n2)\binom{n}{2} unordered pairs is equally likely.

Input

The first line has three integers nn, aa and bb: the number of citizens and the two side lengths of a blanket (2≤n≤200 0002 \le n \le 200\,000, 1≤a,b≤1 000 0001 \le a, b \le 1\,000\,000).

Each of the next nn lines has two integers xix_i and yiy_i, the coordinates of the spot where citizen ii always puts the lower left corner of the blanket (0≤xi,yi≤1 000 0000 \le x_i, y_i \le 1\,000\,000).

Output

Print the expected overlap area on one line as an irreducible fraction: the numerator, one slash, the denominator, with no spaces, in the form p/q. Reduce it so that gcd⁡(p,q)=1\gcd(p, q) = 1 and q≥1q \ge 1, and print the denominator even when it equals 11. If no two blankets overlap, the expected value is 00 and the answer is 0/1. The numerator does not always fit in a signed 64-bit integer.

Hint

The picture shows the arrangement of the first example. The six pairs overlap in areas 44, 00, 00, 11, 66, 00, so the expected value is (4+0+0+1+6+0)/6=11/6(4 + 0 + 0 + 1 + 6 + 0) / 6 = 11/6.

Examples3

  1. Example 1

    Input
    4 3 5
    0 0
    2 1
    3 3
    0 5
    
    Expected output
    11/6
    
  2. Example 2

    Input
    3 3 3
    0 0
    1 1
    2 2
    
    Expected output
    3/1
    
  3. Example 3

    Input
    2 1 1
    0 0
    1000000 1000000
    
    Expected output
    0/1