PAIRDIV - Pair Divisible

no tags 

For two segments of integer [l1, r1] and [l2, r2]. How many pair (x, y) which l1 <= x <= r1 and l2 <= y <= r2 where x * y divisible by p.

Input

The first line is integer p (1 <= p <= 10^9)

Second line includes l1, r1 separated by a space (1 <= l1 <= r1 <= 10^9).

Third line includes l2, r2 separated by a space (1 <= l2 <= r2 <= 10^9).

Output

Result of problem.

Example

Input:
2
1 4
2 6
Output:
16

hide comments
shashwat26: 2017-10-22 18:57:17

ac in one go

:D: 2016-10-05 23:35:19

Re Blue.Mary: see my comment under PAIRDIV2 problem.

[Rampage] Blue.Mary: 2016-03-08 16:56:30

It seems that PAIRDIV2 can't be solved by an O(sqrt(N)) algorithm.

wisfaq: 2016-03-08 16:29:30

In the light of psetter's conduct, and because of the fact we have http://www.spoj.com/problems/PAIRDIV2/ now, it seems best to me to move this one to tutorial

[Rampage] Blue.Mary: 2016-03-08 15:35:44

Recent days rejudging is no longer available for main contest. i.e. Problem setters CANNOT change verdicts after solution has been judged.
P.S. This is NOT justification for this problem setter.

wisfaq: 2016-03-08 12:36:51

When published first constraints were:
Second line includes l1, r1 separated by a space (1 <= l1 <= r1 <= 10^5).
Third line includes l2, r2 separated by a space (1 <= l2 <= r2 <= 10^5).

I had an AC solution for those constraints.
However, problemsetter thought it a good idea to change these constraints AFTER publication.
In itself this isn't very nice to people that invested time in the first version.

However, and I consider this extremely rude, he disqualified my AC solution. I did nothing wrong to get a solution disqualified.
If you want you can rejudge but disqualify: NO.
I consider this an insult.

Last edit: 2016-03-08 14:34:09

Added by:Gầy :))
Date:2016-03-07
Time limit:1s-5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY