Periodical Cicadas

Interview

Time limit1sMemory limit1024 MB

Summary

For each pair of cicadas with cycles c1 and c2 last seen together in year y, find the earliest year any pair reappears together, which is y plus lcm(c1, c2).

Level: Easy3 of 10
Topics: Math, Number theory, Implementation
Solved: No attempts yet

Problem

There are two different species of periodical cicadas that appear from hibernation every $13$ and $17$ years, respectively. Your old grandpa tells you that he saw them simultaneously back in '92. You start pondering how many years you have to wait until you see them again. You collect information about other pairs of periodical cicadas and when they were last observed to find out when the next simultaneous appearance is.

Given several different pairs of cicadas and their last simultaneous appearance, find the next year that one of the pairs reappears.

Input

The first line of input contains a single integer $k$ ( $1 \le k \le 99$ ), the number of pairs of periodical cicadas. Then follow $k$ lines, each containing three integers $y$ , $c_1$ and $c_2$ ( $1800 \le y \le 2021$ , $1 \le c_1, c_2 \le 99$ ), the year this pair was last observed and cycle lengths for the first and second species, respectively. You may assume that none of the $k$ pairs reappears earlier than $2022$ .

Output

Output the first year a pair reappears.

Examples2

Example 1
Input
```
3
1992 13 17
1992 14 18
2001 5 7
```
Expected output
```
2036
```
Example 2
Input
```
2
2020 2 3
2019 3 4
```
Expected output
```
2026
```