← 返回题目列表

Codeforces · 45/B

B. 学校

中文机器翻译题面 查看原题

berland 中学的“B”组有 n 名六年级学生。他们每个人都有一个朋友,当他有消息时他会打电话给他。让我们用 g(i) 来表示编号为 i 的朋友。请注意,友谊不是相互的,即 g(g(i)) 不一定等于 i。

在第 i 天,编号为 ai 的人获悉了评级为 bi 的新闻(bi ≥ 1)。他立即打电话给朋友并告知了此事。当他这样做时,新闻变得旧了,其评级略有下降,变成等于 bi - 1。朋友做了同样的事情 - 他也打电话给他的朋友并告诉了这个消息。朋友的朋友收到的新闻已经被评级为bi-2。这一切都会继续,直到新闻的评级达到零,因为没有人愿意以零评级来讲述新闻。

更正式地说,每个人的行为都是这样的:如果一个人 x 以非零评级 y 得知新闻,他打电话给他的朋友 g(i),他的朋友以 y - 1 的评级得知新闻,如果可能,则继续该过程。

让我们注意到,在一天中,同一个人可能会打电话给他的朋友,告诉他一条相同的新闻,但收视率不同。因此,具有 bi 评级的新闻将导致与 bi 一样多的电话。

你的任务是计算 resi 的值——有多少学生在第 i 天学到了他们的第一个新闻。

bi 的值最初已知,而 ai 由以下公式确定:

$$a_{i} = \left( (v_{i} + res_{i-1} - 1) \mod n \right) + 1,$$

输入

第一行包含两个空格分隔的整数 n 和 m (2 ≤ n, m ≤ 105) — 学生人数和天数。第二行包含 n 个空格分隔的整数 g(i) (1 ≤ g(i) ≤ n, g(i) ≠ i) — 第 i 个学生的朋友的号码。第三行包含 m 个空格分隔的整数 vi (1 ≤ vi ≤ 107)。第四行包含 m 个空格分隔的整数 bi (1 ≤ bi ≤ 107)。

输出

打印 m 行,每行包含一个数字。第 i 行应包含 resi — 对于多少名学生来说,他们在相关 m 天内学到的第一条新闻是新闻号 i。新闻的条数是指可以获悉该条新闻的日期的条数。天数按照输入文件中给出的顺序从 1 开始编号。不输出res0。

示例

输入 #1

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

输出 #1

1
1
1
0

输入 #2

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

输出 #2

1
1
1
2
1
1