В 6Б классе берляндской средней школы учится n ребят. У каждого из них есть ровно один друг, которому он звонит, когда узнает новость. Обозначим друга i-ого человека через g(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 вычисляются по следующей формуле:
В первой строке через пробел записано два целых числа 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 выводить не следует.
3 4
2 3 1
1 2 3 4
1 2 3 4
1
1
1
0
8 6
7 6 4 2 3 5 5 7
10 4 3 8 9 1
1 1 1 2 2 2
1
1
1
2
1
1
