Divan and a Cottage
Contest: Codeforces Round 757 (Div. 2)
Difficulty rating: 2600
Tags: binary search, data structures

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 < T$$$,
- $$$P_{new} = P - 1$$$, if $$$P > T$$$,
- $$$P_{new} = P$$$, if $$$P = T$$$.

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.

Input format:
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$$$.

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

Constraints:
Time limit: 2.0 s
Memory limit: 1024.0 MB

Note:
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 < 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 < 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$$$.

Example input:
3
50
3
1 2 3
50
3
4 5 6
0
3
7 8 9

Example output:
2
5
9
15
22
30
38
47
53

Example input:
4
728
3
859 1045 182
104
1
689
346
6
634 356 912 214 1 1
755
3
241 765 473

Example output:
858
1902
2083
2770
3401
3754
4663
4874
4872
4870
5107
5868
6337

Editorial:
Let $$$ans_{temp}$$$ the current answer for temperature $$$temp$$$. Before all days, $$$ans_{temp}$$$ is considered equal to $$$temp$$$.
In order to respond to a request with a temperature of $$$x$$$, we will just need to output the value of $$$ans_x$$$. But how to maintain $$$ans$$$? With the help of an implicit tree of segments, at the vertices of which the minimum and maximum will be stored, as well as the variable $$$add$$$, which will contain the value that needs to be added to the current vertex (that is, such a variable that is needed to perform lazy operations on the segment tree).
At the beginning of the next day you get the temperature $$$T$$$. Now we need to change the current answer for some $$$temp$$$. We need to find such $$$ans_{temp}$$$ that $$$ans_{temp} <T$$$ and add $$$+1$$$ to them, and then find such $$$ans_{temp}$$$ that $$$ans_{temp} > T$$$ and add $$$-1$$$ to them. All this is not difficult to do, just starting from the root of the segment tree and stopping at the moments when:
• the maximum of the current vertex is less than $$$T$$$ — here we add $$$+1$$$;
• the minimum of the current vertex is greater than $$$T$$$ — here we add $$$-1$$$;
• the minimum of the vertex is equal to the maximum of the vertex (and, therefore, the $$$T$$$ itself) — here we do not add anything.
The resulting asymptotics in time: $$$\mathcal{O}(n\log{}T)$$$.