Prefix Sets

Problem Source

Click here

Problem Description

For a sequence $a$, define its prefix set $S(a, i)$ as the set of the first $i$ elements $a[1]\dots a[i]$.

Given two sequences $a, b$ of length $n$, and $m$ queries. Each query gives two positions $i, j$. You need to determine whether the prefix set $S(a, i)$ equals the prefix set $S(b, j)$.

Input Format

The first line contains an integer $n$ ($n \le 5 \times 10^5$).

The next two lines each contain $n$ integers, describing $a$ and $b$ respectively ($1 \le a_i, b_i \le 10^9$).

The next line contains an integer $m$ ($m \le 5 \times 10^5$).

The following $m$ lines each contain two integers $i$ ($1 \le i \le n$), $j$ ($1 \le j \le n$), representing a query on $S(a, i)$ and $S(b, j)$.

Output Format

Output $m$ lines. For each query, if the two prefix sets are equal, print Y; otherwise print N.

Sample Input

5
1 2 3 4 5
1 2 2 4 3
7
1 1
2 2
2 3
3 3
4 4
4 5
5 5

Sample Output

Y
Y
Y
N
N
Y
N