Problem Description

Xiao Y and Xiao S are playing a game.

Given a positive integer \( m \), a basic set is defined as a set of size 3 with elements ranging from 1 to \( m \). For example, given \( m = 4 \), the sets \(\{1, 2, 3\}\) and \(\{2, 3, 4\}\) are both basic sets.

A set sequence is defined as a sequence composed of basic sets. For example, \( A = [\{1, 2, 3\}, \{2, 3, 4\}] \) is a set sequence, where \( A[1] = \{1, 2, 3\} \) and \( A[2] = \{2, 3, 4\} \) are both basic sets.

For a permutation \( p[1], p[2], \ldots, p[m] \) of the numbers from 1 to \( m \) and a set \( S \subseteq \{1, 2, \ldots, m\} \), define \( f_p(S) \) as the set obtained by replacing each element \( x \) in \( S \) with \( p[x] \), i.e., \( f_p(S) = \{p[x] \mid x \in S\} \).

For two set sequences \( A \) and \( B \) of length \( k \), define \( A \) and \( B \) as equivalent if and only if there exists a permutation \( p \) of the numbers from 1 to \( m \) such that applying \( p \) to \( A \) results in \( B \), i.e., for all \( 1 \leq i \leq k \), \( f_p(A[i]) = B[i] \).

Given two set sequences \( A \) and \( B \) of length \( n \), there are \( q \) queries. Each query asks whether the subsequence \( [A[l], A[l+1], \ldots, A[r]] \) is equivalent to the subsequence \( [B[l], B[l+1], \ldots, B[r]] \) for given \( l \) and \( r \).

Input Format

The first line of input contains three positive integers \( n, m, q \), representing the length of the set sequences, the range of elements, and the number of queries, respectively.

The second line contains \( 3n \) positive integers, where the \( 3i-2, 3i-1, 3i \) (for \( 1 \leq i \leq n \)) integers represent the three elements of \( A[i] \). These elements are guaranteed to be distinct and within the range \([1, m]\).

The third line contains \( 3n \) positive integers, where the \( 3i-2, 3i-1, 3i \) (for \( 1 \leq i \leq n \)) integers represent the three elements of \( B[i] \). These elements are guaranteed to be distinct and within the range \([1, m]\).

The next \( q \) lines each contain two positive integers \( l \) and \( r \), representing a query.

Output Format

Output \( q \) lines, each containing a string "Yes" or "No", indicating whether the corresponding sequences in the query are equivalent.

Sample Input and Output

Input Sample #1

4 4 10
1 2 3 1 2 3 1 2 4 1 2 3
1 2 4 2 3 4 1 2 3 2 3 4
1 1
1 2
1 3
1 4
2 2
2 3
2 4
3 3
3 4
4 4

Output Sample #1

Yes
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes

Input Sample #2

See set2.in/ans
This sample satisfies the constraints of test points 1-3.

Output Sample #2

Input Sample #3

See set3.in/ans
This sample satisfies the constraints of test point 8.

Output Sample #3

Input Sample #4

See set4.in/ans
This sample satisfies the constraints of test points 15, 16.

Output Sample #4

Notes/Hints

[Sample 1 Explanation]

• For query \((1,1)\), let the permutation \( p = [1, 2, 4, 3] \), then \( f_p(A_1) = \{p[1], p[2], p[3]\} = \{1, 2, 4\} = B[1] \), so the sequences are equivalent.
• For queries \((1,2), (1,3), (1,4)\), since \( A[1] = A[2] \) but \( B[1] \neq B[2] \), the sequences are not equivalent.
• For queries \((2,2), (2,3), (2,4), (3,3), (3,4), (4,4)\), let the permutation \( p = [2, 3, 4, 1] \), then \( f_p(A_2) = \{p[1], p[2], p[3]\} = \{2, 3, 4\} = B_2 \), \( f_p(A_3) = \{p[1], p[2], p[4]\} = \{1, 2, 3\} = B_3 \), \( f_p(A_4) = \{p[1], p[2], p[3]\} = \{2, 3, 4\} = B_4 \), so the sequences are equivalent.

[Data Range]

For all test data, it is guaranteed that \( 1 \leq n \leq 2 \times 10^5 \), \( 3 \leq m \leq 6 \times 10^5 \), \( 1 \leq q \leq 10^6 \), \( 1 \leq l \leq r \leq n \).

见题面 Input 部分

见题面 Output 部分