Locust Locus

면접 대비

시간 제한1초메모리 제한1024 MB

요약

마지막 목격 연도 y와 주기 c1, c2가 주어진 여러 쌍에 대해 2021년 이후 두 주기가 동시에 돌아오는 가장 빠른 해를 구한다.

난이도: 보통10점 중 4점
유형: 수학, 정수론
정답자: 아직 제출이 없습니다

문제

There are two different species of periodical cicadas that only 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.

입력

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 the first year a pair reappears.

예제2

예제 1
입력
```
3
1992 13 17
1992 14 18
2001 5 7
```
예상 출력
```
2036
```
예제 2
입력
```
2
2020 2 3
2019 3 4
```
예상 출력
```
2026
```