You are given a tree of N nodes rooted at node 1. The tree will be given as an array p of size (N-1), where p[i] (0<=i<N-1) represents the parent of the (i+1)th node.

Each node also has a value associated with it, given as an array val of size N.

For each node V, you have to calculate the number of nodes in the subtree of V whose value is co-prime with the value of V.

You need to return the sum of this value for all nodes in the tree as an answer.

Constraints
1 <= n <= 100000
1 <= val[i] <= 1000
array p represents a valid tree, rooted at node 1.
Sample Input:
n: 5
par: [1, 1, 3, 3]
val: [1,2,3,4,5]
Sample Output:
6
Sample Explanation:
par array is [1,1,3,3]. This means parent of node 2 and node 3 is 1, and parent of node 4 and node 5 is 3.
val array is [1,2,3,4,5]. This means values of nodes 1,2,3,4 and 5 are 1,2,3,4 and 5 respectively.
The tree looks like this:
Sample Tree
For node 1, the nodes in its subtree whose values are co-prime with value of 1, i.e. 1 are: 2,3,4 and 5. Count: 4
For nodes 2,4 and 5 there are no such nodes as they have no subtree.
For node 3, the nodes in its subtree whose values are co-prime with value of 3 i.e. 3 are: 4 and 5. Count: 2.
So final answer = 4 + 2 = 6.
Input Generation
You are not directly given the arrays p and val. Instead you are given four integers N, seed, l, r and s for randomly generating the arrays p and val. Use the following stub to begin with:
int p[100001], val[100001]; // global arrays which will be randomly generated by below function
void generateTree(int N, int seed, int L, int R, int S) {
srand(seed);
```
for(int i=1;i<=N-1;i++) {
p[i] = max(1, i-S+1) + (rand() % (i+2 - max(1, i-S+1))); // random node in [i-S+1, i+1]
}
```

for(int i=1;i<=N;i++) {
val[i] = L + rand() % (R-L+1); // random integer between L and R
}
}
long long solution(int n, int seed, int l, int r, int s) {
generateTree(n, seed, l, r, s); // Call the random generator to generate p and val arrays first
// Write your code from here
}
[execution time limit] 3 seconds (cpp)
[input] integer n
The number of nodes in the tree. 1 <= n <= 100000
[input] integer seed
parameter for random generation
[input] integer l
parameter for random generation
[input] integer r
parameter for random generation
[input] integer s
parameter for random generation
[output] integer64
The sum of the number of co-prime values in the subtree, for each node.