Заправочные станции
Вам необходимо совершить круговой тур для заданного набора городов: стартовать следует в некотором городе, посетить каждый город один раз, и вернуться в город с которого начиналась поездка.
Каждый город имеет свой номер: 1, 2, 3 и так далее. Порядок нумерации указывает на порядок посещения городов, только начальная точка отправления не указана. Из города с наибольшим номером Вы должны ехать в город 1. Например, если имеются три города (пронумерованных 1, 2, 3), то у Вас имеется три варианта совершить путешествие:
Начать в 1, пойти в 2, затем в 3, и вернуться в 1.
Начать в 2, пойти в 3, затем в 1, и вернуться в 2.
Начать в 3, пойти в 1, затем в 2, и вернуться в 3.
В каждом городе находится заправочная станция с имеющимся в ней количеством топлива. Сумма топлива на всех заправках равна объему топлива, необходимому для совершения всего путешествия. Вы стартуете с пустым баком около одной из заправочных станций. Как только Вы завершите тур и вернетесь в начальный город, у Вас закончится топливо.
Вам следует определить, какой город (или города) могут служить отправной точкой путешествия при условии что топливо не закончится прежде чем Вы вернетесь в первоначальную станцию. Считайте что топливный бак достаточно велик, чтобы вместить в себя все операции заправки топливом.
Входные данные
Состоит из нескольких тестов. Каждый тест состоит из трех строк. Первая строка содержит количество городов. Вторая строка содержит количество топлива, доступного для дозаправки в городах в порядке номеров 1, 2, 3, и так далее. Третья строка содержит количество топлива, необходимого для достижения заправки в следующем городе в следующем порядке: от станции в городе 1 до станции в городе 2, от станции в городе 2 до станции в городе 3 и так далее; последнее число задает объем топлива, которое требуется чтобы проехать от города с последним номером до города номер 1. Все объемы топлива являются положительными целыми числами, заданы в имперских галлонах. Сумма поставок топлива не будет превышать 32-разрядных целых чисел. Существует как минимум два и не более 100000 городов. Последняя строка содержит ноль и не обрабатывается.
Выходные данные
Для каждого теста вывести в отдельной строке список городов, которые могут быть стартовыми при успешном завершении кругового тура. Если таких городов существует несколько, то выводить следует их в возрастающем порядке согласно приведенному в примере формату. Венгерский математик Л.Ловац доказал, что как минимум один стартовый город всегда существует.