외계 일몰

시간 제한2초메모리 제한512 MB

요약

정착지마다 주기가 다른 낮과 밤이 반복될 때, 모든 정착지가 동시에 어두워지는 가장 이른 시각을 구하거나 그런 시각이 없음을 판정한다.

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

문제

인류는 태양계 곳곳의 행성과 위성, 소행성을 비롯해 온갖 모양의 천체에 정착지를 세웠다. 이를 기념해 은하 대통령은 "솔라 나이트"라는 새 기념일을 선포했다. 축제의 순간에 모든 정착지가 동시에 불꽃을 쏘아 올리므로, 그 순간에는 모든 정착지가 어둠 속에 있어야 한다.

우주에서 밤은 간단하지 않다. 정착지마다 하루의 길이가 다르고 일출과 일몰 시각도 다르다. 다만 모든 정착지는 같은 순간에 시계를 켰다. 시계를 켠 순간이 낮일 수도 있고 밤일 수도 있어서, 처음 기록된 일출이 처음 기록된 일몰보다 먼저 올 수도 있고 나중에 올 수도 있다.

시각은 시계를 켠 순간부터 정수 시간 $t = 0, 1, 2, \dots$ 로 센다. 하루가 $H$ 시간인 정착지는 $t$ 시간 뒤에 현지 시각 $t \bmod H$ 에 있다.

대통령의 임기는 자전 주기가 가장 긴 천체를 기준으로 정확히 $1825$ 일이다. 그래서 축제는 처음 $1825 \times H_{\max}$ 시간 안에 열려야 한다. 여기서 $H_{\max}$ 는 정착지의 하루 길이 중 가장 큰 값이다.

모든 정착지가 한꺼번에 어둠 속에 있는 가장 이른 시각을 구하라.

입력

첫째 줄에 정착지의 수 $N$ ( $1 \le N \le 20$ )이 주어진다.

다음 $N$ 개 줄에는 각각 정수 세 개가 주어진다.

$H$ ( $2 \le H \le 100$ ): 이 정착지의 하루가 몇 시간인지 나타낸다.
$R$ 과 $T$ ( $0 \le R, T \le H - 1$ , $R \ne T$ ): 각각 일출 시각과 일몰 시각이다.

현지 시각 $R$ 과 $T$ 에 정착지는 어둠 속에 있다. 일출과 일몰 사이에 엄밀히 놓인 시각, 즉 $R$ 에서 앞으로 나아가 $T$ 에 닿기 전까지의 시각에는 낮이다. $T < R$ 이면 하루의 끝을 지나 $0$ 으로 돌아가며 센다. 나머지 시각은 모두 어둠이다.

출력

시계를 켠 뒤 모든 정착지가 어둠 속에 있는 가장 이른 $t$ 를 출력한다. 단 $0 \le t < 1825 \times H_{\max}$ 를 만족해야 한다. 그런 $t$ 가 없으면 impossible을 출력한다.

예제4

예제 1
입력
```
2
24 7 19
24 18 6
```
예상 출력
```
6
```
예제 2
입력
```
3
10 8 2
15 5 10
20 15 10
```
예상 출력
```
12
```
예제 3
입력
```
2
6 4 2
12 7 5
```
예상 출력
```
impossible
```
예제 4
입력
```
2
10 5 6
10 6 5
```
예상 출력
```
5
```