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:

$\text{[math]}$ 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.

Input

The first line contains two space-separated integers n and m (2 ≤ n, m ≤ 10⁵) — the number of students and the number of days. The second line contains n space-separated integers g(i) (1 ≤ g(i) ≤ n, g(i) ≠ i) — the number of a friend of the i-th student. The third line contains m space-separated integers v_i (1 ≤ v_i ≤ 10⁷). The fourth line contains m space-separated integers b_i (1 ≤ b_i ≤ 10⁷).

Output

Print m lines containing one number each. The i-th line should contain res_i — for what number of students the first news they've learned over the m days in question, was the news number i. The number of the news is the number of the day on which it can be learned. The days are numbered starting from one in the order in which they are given in the input file. Don't output res₀.

School

Examples