As you might already know, Ada the Ladybug is a farmer. She grows a tomel tree. Tomel indeed is a very specific tree. Its growing process starts with one root node with a fruit of random flavor. Whenever a next branch grows, it begins to grow from a random node which is already grown up. No growing starts until the branch is fully grown. As a branch fully grows up, a node with fruit with random flavor appears at the end of the branch.

As you surely haven't heard word random for a long time, Ada chooses three random paths and wants to find the number of distinct flavors which grow on the union of these three paths.

NOTE: Every random mentioned above is really meant to be random with equal probability for each possible values.

Input

The first line of input will contain three integers N, K, Q: 1 ≤ N, Q ≤ 3*10⁵, 1 ≤ K ≤ 1000, the number of nodes of tomel tree, the universe of flavors and the number of Ada's questions.

The next line will contain N-1 integers 0 ≤ P_i < i is the parent of i^th node (here i goes from 1 to N-1).

The next line will contain N integers 1 ≤ F_i ≤ K , the flavor of each fruit.

The next Q lines will contain six integers 0 ≤ B, E, X, Y, L, R< N, where the pairs of beginings/ends of the paths are: (B, E), (X, Y), (L, R)

Output

For each query output the number of distinct flavors which are on the three paths.

Example Input

5 2 5
0 0 0 2
1 1 1 1 2
3 2 3 1 1 4
1 0 2 4 2 3
2 1 4 3 1 0
1 3 3 0 3 1
4 2 0 3 4 1

Example Output

2
2
2
1
2

Example Input

7 3 7
0 0 0 1 2 3
1 3 2 2 2 1 1
3 2 3 6 3 5
0 2 6 0 4 2
3 6 3 0 2 0
2 0 4 0 2 0
1 5 5 3 2 6
1 2 0 5 0 6
0 4 5 3 2 0

Example Output

2
3
2
3
3
3
3

Example Input

8 5 7
0 1 0 1 3 0 3
1 1 4 2 3 1 3 1
1 4 2 3 2 4
3 1 4 2 3 6
6 0 0 7 0 6
3 4 2 1 3 4
5 1 0 1 2 1
5 2 4 5 7 6
2 5 1 6 7 2

Example Output

4
4
3
4
3
4
4

Example Input

12 6 10
0 1 0 2 0 4 4 5 6 6 5
5 4 1 5 3 5 3 5 4 6 4 6
3 9 5 3 5 7
10 8 10 11 6 0
11 6 8 11 3 9
9 2 6 4 8 5
6 5 10 0 2 5
9 11 2 3 2 9
2 3 1 6 10 7
5 2 3 1 9 3
3 4 6 3 6 4
3 8 2 5 0 8

Example Output

5
5
5
5
4
5
4
5
4
3

Example Input

20 10 22
0 1 2 0 4 5 3 6 8 2 7 2 9 8 13 2 16 10 16
6 7 3 10 7 2 10 6 7 3 6 1 1 3 9 9 8 2 9 3
4 13 5 0 17 7
0 2 8 6 8 13
9 19 12 14 5 13
12 14 9 19 5 18
6 4 9 12 2 16
0 1 11 14 14 0
11 4 17 5 1 13
7 16 1 7 8 15
7 1 14 12 8 16
9 8 18 1 4 18
14 8 4 2 2 12
4 16 3 5 10 19
1 6 7 16 11 12
11 0 5 18 12 8
14 17 0 18 3 19
10 12 5 6 4 10
18 19 14 3 15 9
3 9 13 19 1 18
0 5 3 18 1 16
9 19 12 1 13 7
0 2 7 13 16 19
0 11 3 13 12 4

Example Output

6
4
8
8
7
7
7
6
8
4
5
6
7
7
7
6
7
7
7
7
6
6