Alien Sunset

Time limit2sMemory limit512 MB

Summary

Find the earliest time when every settlement is dark on its own periodic day, or report that none exists within the term.

Level: Medium5 of 10
Topics: Math, Number theory, Brute force
Solved: No attempts yet

Problem

Humans have settled planets, moons, asteroids, and other oddly shaped rocks all over the solar system. To mark the occasion the Galactic President declares a new holiday called Solar Night. At the moment of the celebration every settlement launches fireworks at once, so every settlement has to be in darkness at that same moment.

Night is awkward in space. Each settlement has its own day length and its own hours of sunrise and sunset. Every settlement did start its clock at the same moment. A settlement may have started in daylight or in darkness, so the first recorded sunrise can come before or after the first recorded sunset.

Time is counted in whole hours $t = 0, 1, 2, \dots$ from the moment the clocks started. A settlement whose solar day is $H$ hours long is at local hour $t \bmod H$ after $t$ hours.

The President's term lasts exactly $1825$ days as measured by the body with the longest rotation period, so the celebration must happen within the first $1825 \times H_{\max}$ hours, where $H_{\max}$ is the largest day length among the settlements.

Find the earliest hour at which every settlement is in darkness.

Input

The first line contains the integer $N$ ( $1 \le N \le 20$ ), the number of settlements.

Each of the next $N$ lines contains three integers.

$H$ ( $2 \le H \le 100$ ), the number of hours in this settlement's solar day.
$R$ and $T$ ( $0 \le R, T \le H - 1$ , $R \ne T$ ), the hour of sunrise and the hour of sunset.

A settlement is in darkness at local hour $R$ and at local hour $T$ . It is in daylight at the local hours strictly between sunrise and sunset, counting forward from $R$ until $T$ is reached. When $T < R$ the count wraps past the end of the day and continues at hour $0$ . Every other local hour is darkness.

Output

Print the smallest $t$ with $0 \le t < 1825 \times H_{\max}$ such that every settlement is in darkness $t$ hours after the clocks started. If no such $t$ exists, print impossible.

Examples4

Example 1
Input
```
2
24 7 19
24 18 6
```
Expected output
```
6
```
Example 2
Input
```
3
10 8 2
15 5 10
20 15 10
```
Expected output
```
12
```
Example 3
Input
```
2
6 4 2
12 7 5
```
Expected output
```
impossible
```
Example 4
Input
```
2
10 5 6
10 6 5
```
Expected output
```
5
```