GCD-Based Set Queries

Given five positive integers (n, c, f, l,) and (r), define the set (S = {x \in \mathbb{N}_+ \mid \gcd(x, n) \leq c}) and the subset (Q = {x \in S \mid l \leq x \leq r}).

There are two tasks:

1. Find the \(f\)-th smallest number in \(S\).
2. Count the number of elements of \(Q\) (i.e. elements of \(S\) between \(l\) and \(r\), inclusive).

Note: The numbers involved can be very large, so efficiency is required.\n

For any positive integer \(x\), the condition \(x \in S\) is equivalent to having \(\gcd(x, n)\) equal to some divisor \(d\) of \(n\) with \(d \le c\). In fact, if \(\gcd(x, n)=d\) then writing \(x = d \cdot y\) we require \(\gcd(y, n/d)=1\).

Let us define a counting function
\[ F(X)=\sum_{\substack{d\mid n\\ d\le c}} \; \#\{y \le \lfloor X/d\rfloor : \gcd(y, n/d)=1\}\] which counts the number of elements \(x\le X\) that belong to \(S\).

The answers can be obtained by:

1. Using binary search to find the smallest \(X\) such that \(F(X)=f\). This \(X\) will be the \(f\)-th smallest element in \(S\).
2. The count of numbers in \(Q\) is \(F(r)-F(l-1)\).

inputFormat

Input consists of a single line containing five space-separated positive integers: (n, c, f, l, r).

outputFormat

Output two numbers separated by a space: the (f)-th smallest element in (S) and the number of elements in (Q).

sample

6 3 5 1 20

5 17