迪万的新小屋终于完工了!然而,经过彻底检查后发现,工人安装的隔热材料不正确,现在屋内的温度直接取决于室外的温度。更准确地说,如果早上房屋内的温度为 $$$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$$$。