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

N/A

N/A

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