Новый коттедж Divanа наконец-то достроен! Однако после тщательного осмотра было выяснено — рабочие неправильно проложили термоизоляцию, и теперь температура в доме напрямую зависит от температуры на улице! Говоря точнее, если утром в доме была температура \(P\), а на улице температура равна \(T\), то к следующему утру температура в доме изменится по следующему правилу:
- \(P_{new} = P + 1\), если \(P < T\);
- \(P_{new} = P - 1\), если \(P > T\);
- \(P_{new} = P\), если \(P = T\).
Здесь
\(P_{new}\) — температура в доме утром следующего дня.
Divan — очень занятой бизнесмен, поэтому порой не бывает дома продолжительное время и не знает, какая там сейчас температура, поэтому он нанял вас для контроля. Ваша работа будет состоять из \(n\) дней. В начале \(i\)-го дня вам сообщают, что температура на улице в этот день равна \(T_i\). Далее, для каждого из \(i\) дней вам поступает \(k_i\) вопросов от Divan. Каждый запрос имеет следующий вид: «если исходная температура в доме утром первого дня была \(x_i\), то какая температура в доме будет завтра утром (после \(i\)-го дня)?»
Ответьте на все вопросы бизнесмена.
Выходные данные
Для каждого запроса выведите целое число — температуру в доме после \(i\)-го дня.
Примечание
Рассмотрим первые четыре запроса из примера.
В первый день на улице температура равна \(50\), во второй \(50\) и в третий \(0\).
Положим \(lastans = 0\) изначально.
- Начальная температура в доме в первом запросе первого дня равна \((1 \, + \, lastans) \bmod (10^9 + 1) = 1\). После первого дня температура в доме увеличится на \(1\), так как \(1 < 50\). Таким образом, ответ на первый запрос равен \(2\). Тогда \(lastans = 2\).
- Начальная температура в доме во втором запросе первого дня равна \((2 \, + \, lastans) \bmod (10^9 + 1) = 4\). После первого дня температура в доме увеличится на \(1\), так как \(4 < 50\). Таким образом, ответ на второй запрос равен \(5\). Тогда \(lastans = 5\).
- Начальная температура в доме в третьем запросе первого дня равна \((3 \, + \, lastans) \bmod (10^9 + 1) = 8\). После первого дня температура в доме увеличится на \(1\). Таким образом, ответ на третий запрос равен \(9\). Тогда \(lastans = 9\).
- Начальная температура в доме в первом запросе второго дня равна \((4 \, + \, lastans) \bmod (10^9 + 1) = 13\). После первого дня температура увеличится на \(1\). После второго дня температура увеличится на \(1\). Таким образом, ответ на запрос равен \(15\). Тогда \(lastans = 15\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
50
3
1 2 3
50
3
4 5 6
0
3
7 8 9
|
2
5
9
15
22
30
38
47
53
|
|
2
|
4
728
3
859 1045 182
104
1
689
346
6
634 356 912 214 1 1
755
3
241 765 473
|
858
1902
2083
2770
3401
3754
4663
4874
4872
4870
5107
5868
6337
|
|
3
|
2
500000000
3
1000000000 999999999 888888888
250000000
5
777777777 666666666 555555555 444444444 333333333
|
999999999
999999996
888888882
666666656
333333321
888888874
333333317
666666648
|