Equivalence of Set Sequences

Two players, Y and S, are playing a game. You are given a positive integer \(m\) and two sequences of basic sets \(A\) and \(B\) each of length \(n\). A basic set is defined as any set of three distinct integers chosen from \(\{1,2,\dots,m\}\). For example, when \(m=4\), both \(\{1,2,3\}\) and \(\{2,3,4\}\) are basic sets.

A set sequence is a sequence consisting of basic sets. For instance, a sequence \(A=[\{1,2,3\},\{2,3,4\}]\) is a valid set sequence where \(A[1]=\{1,2,3\}\) and \(A[2]=\{2,3,4\}\).

For a permutation \(p\) of \(\{1,2,\dots,m\}\) and any set \(S\subseteq\{1,2,\dots,m\}\), we define \[ f_p(S)=\{p(x)\mid x\in S\}. \]

For two set sequences \(A\) and \(B\) of the same length \(k\), we say \(A\) and \(B\) are equivalent if and only if there exists a permutation \(p\) of \(\{1,2,\dots,m\}\) such that for every \(1\le i\le k\), \[ f_p(A[i])=B[i]. \]

You are given two set sequences \(A\) and \(B\) (each of length \(n\)) and then \(q\) queries. In each query, you are provided two integers \(l\) and \(r\). Your task is to determine whether the subsequence \[ [A[l], A[l+1], \dots, A[r]] \] and \[ [B[l], B[l+1], \dots, B[r]] \] are equivalent.

Note: If a permutation \(p\) exists that satisfies \(f_p(A[i]) = B[i]\) for every \(l \le i \le r\), then output YES; otherwise, output NO.

The equivalence means that the permutation reassigns the elements of all sets in the chosen segment of \(A\) so that they exactly match the corresponding sets in \(B\). Each basic set has exactly three elements, and the order of elements in a set does not matter.

inputFormat

The first line contains three integers \(m\), \(n\) and \(q\) where \(m\) is the maximum element value, \(n\) is the length of each set sequence, and \(q\) is the number of queries.

The next \(n\) lines each contain three distinct integers representing the basic sets of sequence \(A\). Each line corresponds to one basic set.

This is followed by \(n\) lines in the same format representing the basic sets of sequence \(B\).

Then, \(q\) lines follow, each containing two integers \(l\) and \(r\) (1-indexed) representing a query.

outputFormat

For each query, output a single line containing either YES if the subsequences \(A[l\dots r]\) and \(B[l\dots r]\) are equivalent, or NO otherwise.

sample

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

YES
YES