← 返回题目列表

Codeforces · 1614/E

E. 长沙发和小屋

中文机器翻译题面 查看原题

迪万的新小屋终于完工了!然而,经过彻底检查后发现,工人安装的隔热材料不正确,现在屋内的温度直接取决于室外的温度。更准确地说,如果早上房屋内的温度为 $$$P$$$,街道温度为 $$$T$$$,那么到第二天早上,房屋内的温度将根据以下规则变化:

- $$$P_{new} = P + 1$$$,如果 $$$P < T$$$,
- $$$P_{new} = P - 1$$$,如果 $$$P > T$$$,
- $$$P_{new} = P$$$,如果 $$$P = T$$$。

Divan是一个非常忙碌的商人,所以有时他会长时间不在家,不知道现在的气温是多少,所以他雇佣你来寻找。您将工作 $$$n$$$ 天。在第$$$i$$$天开始时,首先向您提供$$$T_i$$$外的温度。之后,在第 $$$i$$$ 天,您将收到 $$$k_i$$$ 查询。每个查询都会询问以下问题:“如果第一天早上房屋内的温度为 $$$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$$$。 Divan 的实际查询由 $$$x_i = (x'_i + Lastans) \bmod (10^9 + 1)$$$ 给出,其中 $$$a \bmod b$$$ 是 $$$a$$$ 除以 $$$b$$$ 时的提醒。回答查询后,将 $$$lastans$$$ 设置为答案。

保证查询总数(所有$$$k_i$$$的总和)不超过$$$2 \cdot 10^5$$$。

输出

对于每个查询,输出一个整数 - $$$i$$$ 天后房屋内的温度。

示例

输入 #1

3
50
3
1 2 3
50
3
4 5 6
0
3
7 8 9

输出 #1

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

输出 #2

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

输出 #3

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$$$。