Поликарп разрабатывает новую версию старой видеоигры «Pac-Man». Хотя ему действительно нравилось играть в оригинальную игру, некоторые ее аспекты ему не нравились, поэтому он решил немного изменить правила.
В версии Поликарпа вы играете за Пакмана, и вам нужно собирать точки, разбросанные по игровому миру, избегая при этом опасных призраков (никаких отличий от оригинала пока нет). Поликарпу не понравилось то, что в оригинале не было спасения от призраков, поэтому в его версии игровой мир разделен на \(n\) безопасных зон с \(m\) односторонними путями между ними. Также гарантируется, что Пакман может достичь любой безопасной зоны из любой другой. Поскольку безопасные зоны безопасны, призраки не могут атаковать Пакмана, пока он там, он находится в опасности только во время прохождения путей. Пакман начинает игру в безопасной зоне \(s\).
Все точки разбросаны по безопасным зонам; первоначально \(i\)-я безопасная зона содержит \(a_i\) точек (и если Пакман находится в безопасной зоне, он может свободно собирать все точки в ней). Точки исчезают после сбора, но после того, как собрана последняя точка в игровом мире, новые точки появляются в безопасных зонах в том же количестве, что и раньше (\(a_i\) новых точек появляется в \(i\)-й зоне). Точки могут быть восстановлены любое количество раз, так что игра по существу бесконечна.
Поликарп уже определил структуру игрового мира и количество точек в каждой безопасной зоне. Теперь он пытается выяснить, достаточно ли сложна игра. В игре есть \(q\) целей, цель \(i\) — собрать по крайней мере \(C_i\) точек с самого начала игры. Поликарп обозначает сложность \(i\)-й цели как минимальное количество раз, которое игрок должен пройти путь между безопасными зонами, чтобы собрать \(C_i\) точек (так как только прохождение пути ставит Пакмана в опасность). Если какой-то путь пройден несколько раз, пока Пакман собирает точки, то он включается в ответ столько же раз.
Помогите Поликарпу рассчитать сложность каждой цели!
Выходные данные
Для каждой цели \(i\) выведите одно целое число — ее сложность (минимальное количество раз, которое игрок должен пройти по некоторому пути, чтобы собрать хотя бы \(C_i\) точек).
Примечание
Рассмотрим первый пример из условия. Чтобы собрать \(5\) точек, игрок должен собрать \(3\) точки в безопасной зоне \(1\) (стартовая безопасная зона), перейти в зону \(3\), собрать \(2\) точки там.
Для того чтобы собрать \(8\) точек, игрок должен собрать \(3\) точки в безопасной зоне \(1\), перейти в зону \(2\), собрать \(1\) точку, перейти в зону \(1\) без получения точек, перейти в зону \(3\), собрать \(2\) точки. Теперь последние точки в мире собраны, так что они восстанавливаются. Игрок может собрать \(2\) точки в безопасной зоне \(3\) и теперь количество собранных точек составляет \(8\).
Рассмотрим второй пример из условия.
Для того чтобы собрать \(7\) точек игрок должен действовать следующим образом: \(2(+3) \rightarrow 3(+2) \rightarrow 4(+2)\). Таким образом будет собрано \(7\) точек.
Для того чтобы собрать \(14\) точек игрок должен действовать следующим образом: \(2(+3) \rightarrow 3(+2) \rightarrow 1(+1) \rightarrow 4(+2) \rightarrow 5(+1)\) восстановление точек \(5(+1) \rightarrow 4 (+2) \rightarrow 2(+3)\). Таким образом будет собрано \(15\) точек.
Для того чтобы собрать \(23\) точки игрок должен действовать следующим образом: \(2(+3) \rightarrow 3(+2) \rightarrow 1(+1) \rightarrow 4(+2) \rightarrow 5(+1)\) восстановление точек \(5(+1) \rightarrow 4(+2) \rightarrow 2(+3) \rightarrow 3(+2) \rightarrow 1(+1)\) восстановление точек \(1(+1) \rightarrow 4(+2) \rightarrow 2(+3)\). Таким образом будет собрано \(24\) точки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4 2 1
3 1 2
1 2
2 1
1 3
3 1
5 8
|
1
3
|
|
2
|
5 7 4 2
1 3 2 2 1
2 3
4 2
3 4
3 1
1 4
5 4
4 5
7 14 23 27
|
2
6
10
13
|
|
3
|
4 4 3 3
2 3 1 4
3 4
4 1
1 2
2 3
13 42 1337
|
3
13
401
|