The start of the school year means that Nathan is solely responsible for walking his dog, Rex. Out of all places, Deer Lake Park, a popular park in Burnaby, is Rex's favourite. However, the park also has many squirrels, which Rex likes to chase.

The park is made of areas, numbered from to , which are linked by paths. The park is connected and each path in the park takes exactly minute to traverse. Additionally, there is squirrel located at each area, and of the areas have a tree, namely areas .

Rex is not friends with the squirrels and will chase them whenever he sees them. When Rex enters an area with a squirrel, the squirrel will run away, using some of the paths, to the nearest area with a tree. If there are multiple areas at the same distance, the squirrel will choose the smaller numbered area. Rex will follow the squirrel until it reaches a tree, at which point the squirrel will climb up and disappear, never to be seen again.

If Rex enters an area with a squirrel while already chasing a squirrel, he will herd them together and chase all of them. It can be shown that the squirrels will all run to the same tree.

Nathan cannot stop Rex from chasing a squirrel and has to follow Rex during his chases. However, when Rex is not chasing any squirrel, he will follow Nathan and can be directed. Nathan can only end their walk when Rex is not chasing any squirrels.

Nathan wants to plan his walks in the park in such a way that he can visit different areas without wasting too much time chasing squirrels. He has questions, where each question is of the form: what is the minimum amount of time to walk from area to area with Rex? All the questions are independent of each other; assume that the squirrels always return to their original areas after each question. Additionally, assume that all actions, other than traversing a path, take negligible time.

#### Constraints

##### Subtask 1 [15%]

##### Subtask 2 [20%]

##### Subtask 3 [20%]

##### Subtask 4 [45%]

No additional constraints.

#### Input Specification

The first line of input contains three integers , , , the number of areas, the number of areas with trees, and the number of questions respectively.

The second line of input contains distinct integers , the areas with trees.

The third line of input contains integers, , meaning there exists a path between and .

The next lines will contain a question as defined above.

Note that this problem will be **online enforced**, meaning that input will be given in an encrypted format. To encrypt the data, the values , in the questions will be given as , , where represents the XOR bitwise operation. Note that is the answer to the latest question, and it is set to before the first such question.

#### Output Specification

For each question, output one line containing the correct answer to it.

#### Sample Input (Encrypted)

```
5 2 3
1 5
1 2 2 3
1 3
2 3
7 0
```

#### Sample Input (Unencrypted)

```
5 2 3
1 5
1 2 2 3
1 3
4 5
2 5
```

#### Sample Output

```
6
5
4
```

#### Explanation for Sample

For the first question, Nathan and Rex start at area 1. Rex chases the squirrel up the tree at area 1. This takes negligible time. They walk to area 2, where Rex chases the squirrel to area 1. This takes 2 minutes. They walk back to area 2 and continue to area 3. This takes 2 minutes. In area 3, Rex chases the squirrel to area 5. This takes 1 minute. They walk back to area 3. This takes 1 minute. The total time is 2 + 2 + 1 + 1 = 6 minutes.

For the second question, Nathan and Rex start at area 4, where Rex chases the squirrel to area 1. This takes 2 minutes. Then they walk to area 2 (the squirrel is already at area 1). This takes 1 minute. Then they walk to area 3, where Rex chases the squirrel to area 5. This takes 2 minutes. Rex stops chasing the squirrel at area 5. The total time is 2 + 1 + 2 = 5 minutes.

For the third question, Nathan and Rex start at area 2, where Rex chases the squirrel to area 1. Then they walk to area 3, where Rex chases the squirrel to area 5. The squirrel runs up the tree at area 5, meaning they have completed their walk. The total time is 4 minutes.

## Comments