There are n students studying in the 6th grade, in group "B" of a berland secondary school. Every one of them has exactly one friend whom he calls when he has some news. Let us denote the friend of the person number i by g(i). Note that the friendships are not mutual, i.e. g(g(i)) is not necessarily equal to i.

On day i the person numbered as a_i learns the news with the rating of b_i (b_i≥1). He phones the friend immediately and tells it. While he is doing it, the news becomes old and its rating falls a little and becomes equal to b_i-1. The friend does the same thing − he also calls his friend and also tells the news. The friend of the friend gets the news already rated as b_i-2. It all continues until the rating of the news reaches zero as nobody wants to tell the news with zero rating.

More formally, everybody acts like this: if a person x learns the news with a non-zero rating y, he calls his friend g(i) and his friend learns the news with the rating of y-1 and, if it is possible, continues the process.

Let us note that during a day one and the same person may call his friend and tell him one and the same news with different ratings. Thus, the news with the rating of b_i will lead to as much as b_i calls.

Your task is to count the values of res_i − how many students learned their first news on day i.

The values of b_i are known initially, whereas a_i is determined from the following formula:

where mod stands for the operation of taking the excess from the cleavage, res₀ is considered equal to zero and v_i − some given integers.

3 4
2 3 1
1 2 3 4
1 2 3 4

1
1
1
0

8 6
7 6 4 2 3 5 5 7
10 4 3 8 9 1
1 1 1 2 2 2

1
1
1
2
1
1