Есть игра, в которой вам нужно перемещаться по лабиринту. Лабиринт состоит из \(n\) платформ, соединенных \(m\) проходами.
Каждая платформа находится на уровне \(l_i\), уровни платформ — целые числа от \(0\) до \(H - 1\). За один шаг, если вы находитесь на платформе \(i\), вы можете остаться на ней или перейти на другую платформу \(j\). Чтобы перейти на платформу \(j\), они должны быть соединены проходом, и их уровни должны быть одинаковыми, то есть \(l_i = l_j\).
После каждого шага уровни всех платформ меняются. Новый уровень платформы \(i\) вычисляется как \(l'_i = (l_i + s_i) \bmod H\), для всех \(i\).
Вы начинаете на платформе \(1\). Найдите минимальное количество шагов, необходимых, чтобы добраться до платформы \(n\).
Выходные данные
Для каждого теста выведите одно целое число, минимальное количество шагов, необходимых, чтобы добраться с платформы \(1\) до платформы \(n\).
Если невозможно добраться до платформы \(n\), выведите \(-1\).
Примечание
Вот как меняются уровни платформ и какие действия нам нужно выполнить в первом примере.
| Платформа 1 | Платформа 2 | Платформа 3 | Действие |
| Шаг 1 | 1 | 9 | 4 | Остаться на платформе 1 |
| Шаг 2 | 3 | 2 | 4 | Остаться на платформе 1 |
| Шаг 3 | 5 | 5 | 4 | Перейти на платформу 2 |
| Шаг 4 | 7 | 8 | 4 | Остаться на платформе 2 |
| Шаг 5 | 9 | 1 | 4 | Остаться на платформе 2 |
| Шаг 6 | 1 | 4 | 4 | Перейти на платформу 3 |
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 3 10
1 9 4
2 3 0
1 2
3 2
1 3
2 1 10
1 2
4 6
1 2
8 7 25
22 14 5 3 10 14 11 1
9 5 4 10 7 16 18 18
2 8
6 3
3 5
7 5
2 6
1 4
4 7
|
6
-1
52
|