No submission language available for this problem.

Description

Input

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

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

Samples

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

2
5
9
15
22
30
38
47
53

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

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

2
500000000
3
1000000000 999999999 888888888
250000000
5
777777777 666666666 555555555 444444444 333333333

999999999
999999996
888888882
666666656
333333321
888888874
333333317
666666648

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