E. Divan и коттедж
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Новый коттедж 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$$$-го дня)?»

Ответьте на все вопросы бизнесмена.

Входные данные

На первой строке находится целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — количество дней.

Далее следуют описание $$$n$$$ дней в следующем формате.

Первая строка описания содержит целое число $$$T_i$$$ ($$$0 \leq T_i \leq 10^9$$$) — температура в этот день.

Вторая строка содержит целое неотрицательное число $$$k_i$$$ ($$$0 \le k_i \le 2 \cdot 10^5$$$) — количество вопросов в этот день.

Третья строка содержит $$$k$$$ целых чисел $$$x'_i$$$ ($$$0 \leq x'_{i} \leq 10^9$$$) — зашифрованные запросы Divanа.

Пусть $$$lastans = 0$$$ изначально. Тогда настоящий запрос задаётся так: $$$x_i = (x'_i + lastans) \bmod (10^9 + 1)$$$, где $$$a \bmod b$$$ — остаток от деления $$$a$$$ на $$$b$$$. После запроса переменной $$$lastans$$$ присваивается значение, равное вашему ответу на текущий запрос.

Гарантируется, что суммарное количество запросов (то есть сумма по всем $$$k_i$$$) не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого запроса выведите целое число — температуру в доме после $$$i$$$-го дня.

Примеры
Входные данные
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
Входные данные
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
Входные данные
2
500000000
3
1000000000 999999999 888888888
250000000
5
777777777 666666666 555555555 444444444 333333333
Выходные данные
999999999
999999996
888888882
666666656
333333321
888888874
333333317
666666648
Примечание

Рассмотрим первые четыре запроса из примера.

В первый день на улице температура равна $$$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$$$.