Tile Cutting: Maximizing Parallelogram Variants

Youssef is a Moroccan tile installer who cuts parallelogram‐shaped tiles from rectangular tiles via a cutting machine. The rectangular tile is placed in the bottom‐left corner of a centimeter‐grid cutting surface, with its edges aligned with the grid lines. The machine may cut along any straight line joining two distinct grid points on the boundary of the tile provided that the two points lie on adjacent edges. The resulting cut-out parallelogram must have each of its four vertices lie strictly on a different side of the rectangle (i.e. none of its edges is collinear with an edge of the rectangle).

It turns out that every such parallelogram (with integer area) is uniquely determined by the following: when a cut is made between, say, the bottom and right boundary, if the chosen points are A = (x,0) (with 0 < x < W) on the bottom edge and B = (W,y) (with 0 < y < H) on the right edge then one may show that the area of the parallelogram is

$$a=(W-x)\,y.$$

In similar fashion the other three types of adjacent‐edge cuts yield a corresponding representation. In fact, one may prove that the number of valid ways to cut a parallelogram of area \(a>1\) is given by

$$f(a)=4\,d(a)-4,$$

where \(d(a)\) is the number of positive divisors of \(a\). (The two divisors \(1\) and \(a\) correspond to cuts that would force a vertex to lie at a corner, which is not allowed.) For \(a=1\) no valid cut exists so we define \(f(1)=0\.

Youssef has tiles of every area between \(a_{lo}\) and \(a_{hi}\) (inclusive). He now wonders: for which area \(a\) in this range can he cut the maximum number of different parallelogram tiles? If there is a tie, choose the smallest area.

Input Format

The input consists of two integers \(a_{lo}\) and \(a_{hi}\) (separated by space) which represent the inclusive range of areas for which tiles are to be cut.

Output Format

Output two integers separated by a space: first, the area \(a\) (with \(a_{lo}\le a\le a_{hi}\)) that allows the maximum number of valid cuts, and second, the corresponding maximum number \(f(a)\) of cutting methods.

Example

For example, if the input is 4 9, then for each \(a\) in \(\{4,5,6,7,8,9\}\):

• \(a=4\): Divisors: \(1,2,4\) so \(f(4)=4\times3-4=8\).
• \(a=5\): (prime) so \(f(5)=4\times2-4=4\).
• \(a=6\): Divisors: \(1,2,3,6\) so \(f(6)=4\times4-4=12\).
• \(a=7\): (prime) so \(f(7)=4\times2-4=4\).
• \(a=8\): Divisors: \(1,2,4,8\) so \(f(8)=12\) as well.
• \(a=9\): Divisors: \(1,3,9\) so \(f(9)=8\).

The maximum is 12 (attained for \(a=6\) and \(a=8\)); hence the answer is 6 12 (choosing the smaller area in a tie).

inputFormat

The input consists of two space‐separated integers \(a_{lo}\) and \(a_{hi}\) (with \(a_{lo} \le a_{hi}\)).

outputFormat

Output two integers separated by a single space: the area \(a\) that gives the maximum number of valid cuts and the value \(f(a)\) representing that maximum number.

sample

4 9

6 12