CF1614E.Divan and a Cottage

Divan's new cottage is finally complete! However, after a thorough inspection, it turned out that the workers had installed the insulation incorrectly, and now the temperature in the house directly depends on the temperature outside. More precisely, if the temperature in the house is $P$ in the morning, and the street temperature is $T$, then by the next morning the temperature in the house changes according to the following rule:

• $P_{new} = P + 1$, if $P \lt T$,
• $P_{new} = P - 1$, if $P \gt T$,
• $P_{new} = P$, if $P = T$.

Here $P_{new}$ is the temperature in the house next morning.

Divan is a very busy businessman, so sometimes he is not at home for long periods and does not know what the temperature is there now, so he hired you to find it. You will work for $n$ days. In the beginning of the $i$-th day, the temperature outside $T_i$ is first given to you. After that, on the $i$-th day, you will receive $k_i$ queries. Each query asks the following: "if the temperature in the house was $x_i$ at the morning of the first day, what would be the temperature in the house next morning (after day $i$)?"

Please answer all the businessman's queries.

迪万的新别墅终于完工了！然而，经过全面检查后发现，工人们错误地安装了隔热层，导致屋内的温度直接受到室外温度的影响。更准确地说，如果某天早晨屋内温度为 $P$，而室外温度为 $T$，那么到第二天早晨，屋内温度将按如下规则变化：

• 若 $P \lt T$，则 $P_{\text{new}} = P + 1$；
• 若 $P \gt T$，则 $P_{\text{new}} = P - 1$；
• 若 $P = T$，则 $P_{\text{new}} = P$。

其中 $P_{\text{new}}$ 表示第二天早晨的屋内温度。

迪万是一位非常忙碌的商人，因此有时会长时间不在家，无法得知当前屋内温度，于是他聘请你来计算该温度。你将工作 $n$ 天。在第 $i$ 天开始时，首先会给你当天的室外温度 $T_i$；随后，在第 $i$ 天内，你将收到 $k_i$ 个查询。每个查询的形式为：“若第一天早晨屋内温度为 $x_i$，那么经过第 $i$ 天后（即第 $i+1$ 天早晨），屋内温度将是多少？”

请回答这位商人的所有查询。

The first line of the input contains the number $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of days.

The following is a description of $n$ days in the following format.

The first line of the description contains an integer $T_i$ ($0 \leq T_i \leq 10^9$) — the temperature on that day.

The second line contains a non-negative integer $k_i$ ($0 \le k_i \le 2 \cdot 10^5$) — the number of queries that day.

The third line contains $k$ integers $x'_i$ ($0 \leq x'_{i} \leq 10^9$) — the encrypted version of Divan's queries.

Let $lastans = 0$ initially. Divan's actual queries are given by $x_i = (x'_i + lastans) \bmod (10^9 + 1)$, where $a \bmod b$ is the reminder when $a$ is divided by $b$. After answering the query, set $lastans$ to the answer.

It is guaranteed that the total number of queries (the sum of all $k_i$) does not exceed $2 \cdot 10^5$.

输入的第一行包含一个整数 $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_i$ 个整数 $x'_i$（$0 \leq x'_{i} \leq 10^9$），表示 Divan 查询的加密版本。

令初始时 $lastans = 0$。Divan 的实际查询为 $x_i = (x'_i + lastans) \bmod (10^9 + 1)$，其中 $a \bmod b$ 表示 $a$ 除以 $b$ 所得的余数。每次回答完一个查询后，需将 $lastans$ 更新为该次查询的答案。

保证查询总数（即所有 $k_i$ 之和）不超过 $2 \cdot 10^5$。

For each query, output a single integer — the temperature in the house after day $i$.

对于每个查询，输出一个整数——第 $i$ 天后屋内的温度。

Let's look at the first four queries from the example input.

The temperature is $50$ on the first day, $50$ on the second day, and $0$ on the third day.

Note that $lastans = 0$ initially.

• The initial temperature of the first query of the first day is $(1 \, + \, lastans) \bmod (10^9 + 1) = 1$. After the first day, the temperature rises by $1$, because $1 \lt 50$. So the answer to the query is $2$. Then, we set $lastans = 2$.
• The initial temperature of the second query of the first day is $(2 \, + \, lastans) \bmod (10^9 + 1) = 4$. After the first day, the temperature rises by $1$, because $4 \lt 50$. So the answer to the query is $5$. Then, we set $lastans = 5$.
• The initial temperature of the third query of the first day is $(3 \, + \, lastans) \bmod (10^9 + 1) = 8$. After the first day, the temperature rises by $1$. So the answer to the query is $9$. Then, we set $lastans = 9$.
• The initial temperature of the first query of the second day is $(4 \, + \, lastans) \bmod (10^9 + 1) = 13$. After the first day, the temperature rises by $1$. After the second day, the temperature rises by $1$. So the answer to the query is $15$. Then, we set $lastans = 15$.

我们来看示例输入中的前四个查询。

第一天的温度为 $50$，第二天的温度为 $50$，第三天的温度为 $0$。

注意：初始时 $lastans = 0$。

• 第一天的第一个查询的初始温度为 $(1 \, + \, lastans) \bmod (10^9 + 1) = 1$。经过第一天后，温度上升 $1$，因为 $1 \lt 50$。因此该查询的答案为 $2$。然后，我们将 $lastans$ 更新为 $2$。
• 第一天的第二个查询的初始温度为 $(2 \, + \, lastans) \bmod (10^9 + 1) = 4$。经过第一天后，温度上升 $1$，因为 $4 \lt 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$。