Hide

Problem D
Bike Gears

/problems/bikegears/file/statement/en/img-0001.png
Image by Keithonearth (Wikimedia Commons), CC BY-SA 3.0

Many multi-gear (multi-speed) bicycles have a drivetrain mechanism that is structured as follows: the pedals are attached to a front set of sprockets (toothed wheels), which is connected by a chain to a back set of sprockets, which in turn is attached to the rear wheel. The chain can shift, under the cyclist’s control, to any one of the front sprockets and to any one of the back sprockets (sometimes there are mechanical limitations that preclude certain front-back combinations, but we don’t have to worry about that here). As the cyclist moves the pedals forward, the force is transferred from the pedals to the selected front sprocket, to the chain, to the selected back sprocket, and finally to the rear wheel; it is the motion of the rear wheel that drives the bike forward.

The gear the bike is in at any point in time is given by the ordered pair $(f,b)$, where $f$ is the number of teeth on the currently selected front sprocket, and $b$ is the number of teeth on the currently selected back sprocket. The ratio $f/b$ is used to compare gears. A higher (respectively, lower) ratio corresponds to a higher (respectively, lower) gear. Therefore, for example, to change into a lower gear, the cyclist can shift the chain either onto a smaller front sprocket or onto a larger back sprocket (or both). Most cyclists change gears easily and intuitively in response to variations in terrain. However, for bicycles with a relatively large number of gears, figuring out how to progress through the gears in order from lowest to highest can be surprisingly non-obvious, and in fact most cyclists likely do not know how to do this.

Given information about the front and back sprockets on a bicycle with the drivetrain structure described above, your task is to determine the exact sequence of $(f,b)$ sprocket pairs that a cyclist would need to select to progress, in order, through all the gears from lowest to highest. If two different gears, $(f_1, b_1)$ and $(f_2, b_2)$, yield the same ratio, then the gear with the lower $f$ value is considered to be the lower of the two gears.

Input

The input contains a single test case given on three lines. The first line contains two space-separated integers, $F$ and $B$ ($1 \leq F,B \leq 50$), the number of front sprockets and the number of back sprockets, respectively. The second line contains $F$ distinct space-separated integers in decreasing order, the number of teeth on each of the front sprockets. The third line contains $B$ distinct space-separated integers in decreasing order, the number of teeth on each of the back sprockets. Every sprocket has between $4$ and $10^9$ teeth, inclusive.

Output

Output one line for each of the $F \cdot B$ gears. Give these in order from the lowest gear to the highest gear. Each line has five parts: an opening parenthesis (‘(’), an integer $f$ (the number of teeth on one of the front sprockets), a comma (‘,’), an integer $b$ (the number of teeth on one of the back sprockets), and a closing parenthesis (‘)’).

Sample Input 1 Sample Output 1
3 2
20 16 8
5 4
(8,5)
(8,4)
(16,5)
(16,4)
(20,5)
(20,4)

Please log in to submit a solution to this problem

Log in