Longest Contiguous Expressible Subarray

You are given three positive integers n, p, and q. Consider the set of all integers from 1 to n (inclusive). Your task is to determine the length of the longest contiguous subarray such that every element in the subarray can be expressed as a linear combination of p and q with nonnegative integer coefficients.

In mathematical terms, for each integer x in the subarray, there exist nonnegative integers a and b such that:

\( x = a \times p + b \times q \)

According to the Frobenius Coin Problem, if \(p\) and \(q\) are coprime (i.e. \(\gcd(p,q)=1\)), then every integer can be expressed in such a form (with the understanding that for very small numbers, this condition is relaxed for the purpose of this problem). In our problem, you can assume that if \(\gcd(p,q)=1\), then every integer between 1 and n is expressible and the answer would be n; otherwise, if \(p\) and \(q\) are not coprime, then output 0.

Note: The input will be provided via standard input and the output should be written to standard output.

inputFormat

The input consists of a single line containing three space-separated integers: n, p, and q.

Constraints:

• 1 ≤ n ≤ 10⁶
• 1 ≤ p, q ≤ 10⁶

outputFormat

Output a single integer which is the length of the longest contiguous subarray of integers from 1 to n (inclusive) such that every element of the subarray can be expressed as a sum of multiples of p and q.

If p and q are coprime, output n; otherwise, output 0.

## sample

10 2 3

10

</p>