CF45B.School

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_0 is considered equal to zero and v__i — some given integers.

有 $n$ 名学生在某伯兰中学六年级 B 班学习。每名学生恰好有一名朋友，当他自己得知某条消息时，会立即给这名朋友打电话通知。我们用 $g(i)$ 表示编号为 $i$ 的学生的朋友。注意：这种“朋友关系”并非相互的，即 $g(g(i))$ 不一定等于 $i$。

在第 $i$ 天，编号为 $a_i$ 的学生得知一条评分为 $b_i$（其中 $b_i \geq 1$）的消息。他立刻给自己的朋友打电话告知该消息；在此过程中，消息因传播而略微变旧，其评分下降为 $b_i - 1$。该朋友收到消息后，也立即给自己的朋友打电话转告，此时消息评分为 $b_i - 2$。如此继续传播下去，直到消息评分为 $0$ 为止（因为没有人愿意传播评分为 $0$ 的消息）。

更形式化地说，每个人的行为如下：若某人 $x$ 以非零评分 $y$ 得知某条消息，则他立即致电其朋友 $g(x)$，使得该朋友以评分 $y-1$ 得知该消息，并在可能的情况下继续这一过程。

需要注意的是，在同一天内，同一人可能多次给自己的朋友打电话，传递同一条消息但评分不同。因此，一条初始评分为 $b_i$ 的消息总共将引发 $b_i$ 次电话呼叫。

你的任务是计算 $res_i$ 的值——即在第 $i$ 天首次得知消息的学生人数。

所有 $b_i$ 的值在输入中已知，而 $a_i$ 则由如下公式确定：

其中 $\bmod$ 表示取模运算（即除法后的余数），规定 $res_0 = 0$，且 $v_i$ 是给定的整数。

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 v__i (1 ≤ v__i ≤ 107). The fourth line contains m space-separated integers b__i (1 ≤ b__i ≤ 107).

第一行包含两个用空格分隔的整数 $n$ 和 $m$（$2 \leq n, m \leq 10^5$）—— 分别表示学生人数和天数。
第二行包含 $n$ 个用空格分隔的整数 $g(i)$（$1 \leq g(i) \leq n$，且 $g(i) \neq i$）—— 表示第 $i$ 个学生的友人编号。
第三行包含 $m$ 个用空格分隔的整数 $v_i$（$1 \leq v_i \leq 10^7$）。
第四行包含 $m$ 个用空格分隔的整数 $b_i$（$1 \leq b_i \leq 10^7$）。

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.

输出 m 行，每行一个数字。第 i 行应包含 res__i —— 即：有多少名学生在所给的 m 天中，首次获知的新闻恰好是编号为 i 的新闻。新闻的编号即为其可被获知的那一天的序号（输入文件中给出的天数按顺序从 1 开始编号）。请勿输出 _res_0。