Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. School

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere 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:

Input

The first line contains two space-separated integers *n* and *m* (2 ≤ *n*, *m* ≤ 10^{5}) — 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^{7}). The fourth line contains *m* space-separated integers *b* _{ i} (1 ≤ *b* _{ i} ≤ 10^{7}).

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* _{0}.

Examples

Input

3 4

2 3 1

1 2 3 4

1 2 3 4

Output

1

1

1

0

Input

8 6

7 6 4 2 3 5 5 7

10 4 3 8 9 1

1 1 1 2 2 2

Output

1

1

1

2

1

1

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/12/2020 06:29:26 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|