Spaceship Meeting Point

The Earth Alliance has built roads with imperfections due to funding restrictions. In particular, each road imposes a certain performance requirement on spaceships that traverse it.

Louis Paosen is organizing a grand three‐person KFC basketball tournament. Teams must be formed using three different types of spaceships: the first member uses type A, the second uses type B, and the third uses type C (this order brings bonus points due to advertising contracts). Although each three‐person team has the correct spaceship types, they may originate from different planets, and due to limitations in spaceship performance, they might not be able to all reach a particular meeting planet.

Each planet u is assigned three coefficients: P_A[u], P_B[u], and P_C[u]. For any bidirectional road connecting planet u and planet v, the difficulty for a spaceship of type X to traverse the road is given by:

$$\text{Difficulty}_{X}(u,v)=P_{X}[u] \oplus P_{X}[v] $$

A spaceship of type X (with performance index f) can pass a road if f \ge \text{Difficulty}_{X}(u,v).

You are given a network of planets and roads. There are three coefficient arrays (one for each spaceship type) provided for the planets. Then, for each query (each team), you are given the starting planet and the performance index for each spaceship. A meeting point is any planet to which all three spaceships can travel via some valid path (using roads that they can individually traverse under their performance limits). Your task is to determine the number of possible meeting planets for each team.

Input Format: The first line contains three integers n, m, and q, where n is the number of planets (numbered 1 through n), m is the number of bidirectional roads, and q is the number of queries (teams).

The next three lines each contain n integers. The first of these lines is the array PA, the second is PB, and the third is PC.

The following m lines each contain two integers u and v indicating that there is a road between planet u and planet v.

Then, there are q lines follow. Each query consists of six integers: a fA b fB c fC. This means that the spaceship of type A starts at planet a with performance fA, type B starts at planet b with performance fB, and type C starts at planet c with performance fC.

Output Format: For each query, output on a separate line a single integer representing the number of planets that can serve as a meeting point (i.e. are reachable by all three spaceships under the given constraints).

inputFormat

The input begins with three integers n m q.

The next three lines each contain n integers, corresponding to arrays PA, PB, and PC respectively.

Then follow m lines, each containing two integers u and v indicating a road between planets u and v.

After that, there are q queries. Each query consists of six integers: a fA b fB c fC, meaning spaceship A starts at planet a with performance fA, spaceship B starts at planet b with performance fB, and spaceship C starts at planet c with performance fC.

outputFormat

For each query, output a single integer on a new line that denotes the number of planets that can be chosen as the meeting point (i.e. planets reachable by all three spaceships under their performance constraints).

sample

4 4 2
1 2 3 4
4 3 2 1
5 5 6 6
1 2
2 3
2 4
3 4
1 3 2 3 4 1
4 4 1 7 1 10

1
1

</p>