5534: School
内存限制：256 MB
时间限制：2 S
题面：传统
评测方式：文本比较
上传者：
提交：0
通过：0
题目描述
B. School
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
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 ai learns the news with the rating of bi (bi≥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 bi-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 bi-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 bi will lead to as much as bi calls.
Your task is to count the values of resi − how many students learned their first news on day i.
The values of bi are known initially, whereas ai is determined from the following formula:
where mod stands for the operation of taking the excess from the cleavage, res0 is considered equal to zero and vi − some given integers.
On day i the person numbered as ai learns the news with the rating of bi (bi≥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 bi-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 bi-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 bi will lead to as much as bi calls.
Your task is to count the values of resi − how many students learned their first news on day i.
The values of bi are known initially, whereas ai is determined from the following formula:
where mod stands for the operation of taking the excess from the cleavage, res0 is considered equal to zero and vi − some given integers.
Input
The first line contains two space-separated integers n and m (2≤n,m≤105) − 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 vi (1≤vi≤107). The fourth line contains m space-separated integers bi (1≤bi≤107).
Output
Print m lines containing one number each. The i-th line should contain resi − 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 res0.
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
输入样例 复制
输出样例 复制