Тимур находится в машине, двигающейся по числовой прямой от точки \(0\) до точки \(n\). Машина начинает движение из точки \(0\) в минуту \(0\).
На прямой находится \(k+1\) знак в точках \(0, a_1, a_2, \dots, a_k\), и Тимур знает, что машина прибудет туда в минуты \(0, b_1, b_2, \dots, b_k\) соответственно. Последовательности \(a\) и \(b\) возрастающие, причем \(a_k = n\).
Машина движется с постоянной скоростью между любыми двумя соседними знаками. У Тимура есть \(q\) запросов: каждый запрос будет целым числом \(d\), и Тимур хочет, чтобы вы вывели, сколько минут машина затратит, чтобы добраться до точки \(d\), округленное в меньшую сторону.
Выходные данные
Для каждого запроса выведите одно целое число — количество минут, затраченных на достижение машиной точки \(d\), округленное в меньшую сторону.
Примечание
В первом примере машина проходит от точки \(0\) до точки \(10\) за \(10\) минут, поэтому скорость составляет \(1\) единицу в минуту и:
- В точке \(0\) время будет \(0\) минут.
- В точке \(6\) время будет \(6\) минут.
- В точке \(7\) время будет \(7\) минут.
Во втором примере машина движется со скоростью \(1\) единицу в минуту между точками \(0\) и \(4\), и со скоростью \(2\) единицы в минуту между \(4\) и \(10\) и:
- В точке \(6\) время будет \(5\) минут.
- В точке \(4\) время будет \(4\) минут.
- В точке \(2\) время будет \(2\) минут.
- В точке \(7\) время будет \(5.5\) минут, поэтому ответ — \(5\).
В четвёртом примере машина движется со скоростью \(1.2\) единицы в минуту, поэтому ответы на запросы:
- В точке \(2\) время будет \(1.66\dots\) минут, поэтому ответ — \(1\).
- В точке \(6\) время будет \(5\) минут.
- В точке \(5\) время будет \(4.16\dots\) минут, поэтому ответ — \(4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
10 1 3
10
10
0
6
7
10 2 4
4 10
4 7
6
4
2
7
1000000000 1 1
1000000000
1000000000
99999999
6 1 3
6
5
2
6
5
|
0 6 7
5 4 2 5
99999999
1 5 4
|