## ADATOMEL - Ada and Tomel

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 ^{5}, 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**node (here

^{th}**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

Added by: | Morass |

Date: | 2017-10-30 |

Time limit: | 2s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All |