Background

In the year 3100, the Earth Alliance has completed the construction of roads within the Milky Way, connecting N planets through a network of N-1 bidirectional space tunnels, forming an undirected complete graph.

Louis Paosen is an interstellar traveler. Last time, you helped him solve a difficult problem, and now he's back asking for your assistance again.

Problem Description

Due to financial constraints, the Earth Alliance was unable to perfect all the roads. Each road imposes certain requirements on the performance of spacecraft.

Louis Paosen has organized a grand KFC three-on-three basketball tournament within the alliance, attracting many participants from different planets.

There are three types of spacecraft (A/B/C) being sold within the Earth Alliance. Due to advertising fees, teams are required to use specific spacecraft: the first player uses type A, the second uses type B, and the third uses type C (to gain bonus points).

Many three-person teams are preparing to compete, equipped with the required spacecraft. However, they may come from different planets, and due to the limitations of their spacecraft's performance, they may not be able to reach a common planet together.

The three companies have vastly different manufacturing techniques, resulting in significant differences in the tolerance of their spacecraft to the same road environment, following peculiar patterns.

Each planet \( u \) has three sets of coefficients \( P_A[u], P_B[u], P_C[u] \). The difficulty of passing an edge \( u \leftrightarrow v \) is:

\[ \begin{cases} \text{Difficulty for type A spacecraft} = P_A[u] \ \text{xor} \ P_A[v] \\ \text{Difficulty for type B spacecraft} = P_B[u] \ \text{xor} \ P_B[v] \\ \text{Difficulty for type C spacecraft} = P_C[u] \ \text{xor} \ P_C[v] \end{cases} \]

A spacecraft can pass a road if its performance index is not lower than the corresponding difficulty for that road (see sample explanation for details).

Louis Paosen has prepared competition points on each planet, so you just need to determine the number of feasible meeting points for each three-person team.

Input Format

The first line contains \( n \) and \( q \).

The next three lines contain \( P_A[1 \sim n] \), \( P_B[1 \sim n] \), and \( P_C[1 \sim n] \), respectively.

The following \( q \) lines each contain six numbers \( h_A, u_A, h_B, u_B, h_C, u_C \), representing the performance of each team member's spacecraft and their starting planet.

Output Format

For each three-person team, output a single line with the number of feasible meeting points.

Sample Input and Output

Input Sample #1

3 3
1 2 3
3 2 1
4 2 2
5 1 2 2 3 3
3 3 3 3 3 3
6 3 5 2 3 1

Output Sample #1

2
2
1

Input Sample #2

10 10
43 24 8 66 96 25 43 87 62 8 
80 25 94 72 43 18 94 96 11 54 
19 25 92 87 76 36 89 91 69 22 
82 2 82 5 82 3
70 10 96 8 70 8
52 7 23 5 52 10
85 1 62 4 85 5
1 5 49 7 1 6
32 7 54 8 32 9
6 1 89 4 6 10
82 10 38 5 82 7
87 2 1 10 87 2
12 3 77 5 12 8

Output Sample #2

10
7
0
5
0
1
1
5
1
1

Notes/Hints

• Property ①: \( P_C[1 \sim n] \) are all equal;
• Property ②: \( P_B[1 \sim n] \) are all equal;
• Property ③: \( P_A[1 \sim n], P_B[1 \sim n], P_C[1 \sim n] \in \{0,1\} \).

(#1~#9 each worth 6 points, #10~#13 worth a total of 46 points; #1~#7 have a space limit of 500MB, other test points have a space limit of 125MB).

All numbers in the input are integers within \([0, 10^8]\).

Sample 1 Explanation

The three performance graphs are shown above.

For example, in the A graph:
\[ \begin{cases} (1,2) = P_A[1] \ \text{xor} \ P_A[2] = 3; \\ (1,3) = P_A[1] \ \text{xor} \ P_A[3] = 2; \\ (2,3) = P_A[1] \ \text{xor} \ P_A[2] = 1; \end{cases} \]

(The way edges are generated is by XORing the corresponding coefficients from the arrays)

For the first team:

• The A spacecraft starting from planet 1 has a performance of 5, capable of reaching all planets.
• The B spacecraft starting from planet 2 has a performance of only 2, unable to pass through edge \((3,2) = 3\), but can still reach all planets.
• The B spacecraft starting from planet 3 has a performance of only 3, able to pass through edge \((2,3) = 0\), and can reach planets 2 and 3.
• In summary, the first team can reach 2 common planets.

见题面 Input 部分

见题面 Output 部分