The problem requires to process queries asking whether \(\{A_l,A_{l+1},\ldots,A_r\}\) coincides \(\{B_L,B_{L+1},\ldots,B_R\}\) as a multiset.

A famous way to determine if two sets are equal fast but probabilistically is Zobrist Hash. Decision of equivalence of two multisets can also be solved fast using hashes likewise.

It is ideal that a hash function \(H\) meets the following requirements:

• The hash value \(H(S)\) of a multiset can be computed fast.
• If two multisets \(S\) and \(T\) are equal, then \(H(S)=H(T)\).
• If two multisets \(S\) and \(T\) are not equal, then \(H(S)\neq H(T)\) with a high probability.

For example, one can assign an arbitrary hash value to each integer between \(1\) and \(N\), and define the hash function of \(S\) to be “the sum of hash values of the elements in \(S\), modulo \(P\) (where \(P\) is an arbitrary large prime) to fulfill the requirements above.

For the first requirement, the hash values of \(\{A_l,A_{l+1},\ldots,A_r\}\) and \(\{B_L,B_{L+1},\ldots,B_R\}\) can be computed in \(O(1)\) time by precalculating the cumulative sums of the hash values. For the second requirements, it is obvious that if two multisets \(S\) and \(T\) are equal, then \(H(S)=H(T)\). Proving the third is quite difficult, but if two multisets \(S\) and \(T\) are not equal, then \(H(S)\neq H(T)\) with a high probability. (Maybe one can use Schwartz–Zippel lemma. [Reference: article by noshi (Japanese)])(https://github.com/noshi91/blog/blob/master/pages/hash.pdf)).

As described so far, by determining the hash value for each integer between \(1\) and \(N\), and precalculating the cumulative sums, the correct answer to each query can be found in \(O(1)\) time. The overall time complexity is \(O(N+Q)\).

import random
mod = (1 << 61) - 1

N, Q = map(int, input().split())
A = list(map(lambda x: int(x) - 1, input().split()))
B = list(map(lambda x: int(x) - 1, input().split()))

hash = [random.randint(1, mod - 1) for i in range(N)]
cumA = [0] * (N + 1)
cumB = [0] * (N + 1)
for i in range(N):
    cumA[i + 1] = (cumA[i] + hash[A[i]]) % mod
    cumB[i + 1] = (cumB[i] + hash[B[i]]) % mod

for i in range(Q):
    l, r, L, R = map(int, input().split())
    if (cumA[r] - cumA[l - 1]) % mod == (cumB[R] - cumB[L - 1]) % mod:
        print("Yes")
    else:
        print("No")