Square Difference Pair Elimination

You are given three integers a, b and T. Consider all the integers in the closed interval \([a,b]\). You can remove any pair of distinct numbers \(x,y\) (with \(x>y\)) if they satisfy the following conditions:

• The difference of their squares is a perfect square, i.e. \(x^2-y^2=z^2\) for some integer \(z\) (in \(\LaTeX\): \(x^2-y^2=z^2\)).
• The number \(y\) and \(z\) are coprime, i.e. \(\gcd(y,z)=1\).

If you remove such a pair \((x,y)\), you earn a score of \(x+y\) points. Each number can be used at most once. Your task is to choose a set of pairs (i.e. a matching on these numbers) so that the number of pairs eliminated is maximized. Among all such matchings, you want to maximize the total score.

Finally, you need to check whether the maximum total score is at least the target score T (which is the requirement for passing the level). Print the maximum number of pairs, the maximum total score, and output Yes if the total score is at least T or No otherwise.

Note on the condition: Since \(x^2-y^2=(x+y)(x-y)\), the condition \(x^2-y^2=z^2\) can be interpreted as finding two positive integers \(d\) and \(s\) both perfect squares such that \(x-y=d\) and \(x+y=s\) (with \(s>d\)); then \(x=\frac{s+d}{2}\) and \(y=\frac{s-d}{2}\). Also, the condition \(\gcd(y,z)=1\) must hold, where \(z=\sqrt{s\cdot d}\).

inputFormat

The input consists of a single line with three space‐separated integers: a, b and T \( (a \le b)\).

Constraints: The size of the interval \([a,b]\) is small (for example, \(b-a+1\) up to 20) so that a bitmask dynamic programming solution is feasible.

outputFormat

Output three items separated by spaces in one line:

1. The maximum number of pairs that can be eliminated.
2. The maximum total score obtained by eliminating those pairs.
3. Yes if the total score is at least T, or No otherwise.

sample

1 10 9

1 9 Yes