Егор с друзьями гуляли по городу и нашли карту метро. В этом городе целых n веток метро, у каждой ветки свое расписание. Изучив расписание, они обнаружили, что по ветке i поезд начинает ходить в aᵢ секунду с начала дня, и каждый новый поезд начинает маршрут после предыдущего спустя bᵢ секунд. Теперь им захотелось научиться в некоторые моменты времени для ветки и времени определять, когда они увидят поезд после прихода на станцию. Формат входных данных В первой строке входных данных дано число n - количество веток в городе (1≤ n ≤ 100) . В следующих n строках даны числа aᵢ, bᵢ - первый момент, когда поезд с i-й ветки приезжает на станцию, и промежуток между поездами (0 ≤ aᵢ < bᵢ ≤ 10⁹). В следующей строке дано число q - количество запросов (1 ≤ q ≤ 100). В следующих q строках даны числа tᵢ, dᵢ - номер ветки и момент времени, когда друзья придут на станцию (1 ≤ tᵢ ≤ n, 1 ≤ dᵢ ≤ 10⁹) Формат выходных данных: Для каждого запроса выведите в отдельной строке ответ на задачу.

Пример входных данных: 3 0 5 2 3 1 7 3 1 4 2 5 3 10

Пример выходных данных: 4 5 10

Объяснение: Для первого запроса (ветка 1, время прихода на станцию 4) первый поезд на ветке 1 приезжает на станцию в момент времени 0, затем каждые 5 секунд. Таким образом, ближайший поезд будет через 4 секунды после прихода на станцию. Для второго запроса (ветка 2, время прихода на станцию 5) первый поезд на ветке 2 приезжает на станцию в момент времени 2, затем каждые 3 секунды. Таким образом, ближайший поезд будет через 5 секунд после прихода на станцию. Для третьего запроса (ветка 3, время прихода на станцию 10) первый поезд на ветке 3 приезжает на станцию в момент времени 1, затем каждые 7 секунд. Таким образом, ближайший поезд будет через 9 секунд после прихода на станцию.