The Hungry Muto

Time limit1.5sMemory limit512 MB

Summary

Given an evolution map on n ingredients, answer Q queries: count starting ingredients x where one evolution step gives the same result as c evolution steps.

Level: Medium5 of 10
Topics: Graph, Number theory
Solved: No attempts yet

Problem

Muto often gathers ingredients and cooks meals to eat. Today he was very hungry as usual. Nearby, he saw $n$ different Pokemon ingredients numbered from $1$ to $n$ . Evolving an ingredient once turns it into another Pokemon ingredient. Bored while cooking, Muto asked you the following question $Q$ times.

Pidori and Pimi start a game with ingredient $x$ . Pidori evolves ingredient $x$ once, and Pimi evolves ingredient $x$ $c$ times. Count the number of values of $x$ for which Pidori's result equals Pimi's result.

Solve the $Q$ questions.

Input

The first line contains the number of ingredients $n$ . The second line contains $n$ integers separated by spaces. The $i$ -th integer $x_{i}$ ( $1 \le x_{i} \le n$ ) means that when ingredient $i$ evolves once, it becomes ingredient $x_{i}$ . The ingredient before and after evolution may be the same.

The next line contains the number of questions $Q$ . The next $Q$ lines each contain a value $q$ , which means that $c$ equals $q$ in that question.

Output

Print the answer to each of Muto's $Q$ questions on its own line.

Constraints

$1 \le n \le 500\,000$

$1 \le Q \le 500\,000$

$1 \le q \le 2\,000\,000$

Examples2

Example 1
Input
```
3
1 3 2
2
1
2
```
Expected output
```
3
1
```
Example 2
Input
```
2
1 2
2
3
4
```
Expected output
```
2
2
```