You are given the following:

• An integer $m$
• An array $a_1,\ a_2,\ \dots ,\ a_n$
• Integers from $1$ to $m$

For every number $c$ in range $[1:m]$, you know its happiness is $h_c$. A subarray is called happy, if for every number $c$ in this subarray, the occurrence of $c$ is equal to $h_c$. 

You are given $q$ queries. The $i^{th}$ query consists of two numbers $l, r$. Your task is to determine if subarray $a_l,\ a_{l+1},\ ...,\ a_r$ is happy or not.

Input format

• The first line contains two integers $n$ and $m$ denoting the length of the array and constant number.
• The second line contains $n$ numbers $a_1,\ a_2,\ \dots,\ a_n$ denoting the elements of the array.
• The third line contains $m$ numbers $h_1,\ h_2,\ \dots,\ h_m$ denoting the elements of the array.
• The next line contains a number $q$.
• The next $q$ lines describe queries and contain two integers $l, r$.

Output format

For each query, print 1 if subarray $a_l,\ a_{l+1},\ \dots,\ a_r$is happy. Otherwise, print 0.

Constraints

$1 \le n, m, q \le 5\times10^5$

$1 \le a_i \le m$

$1 \le h_i \le n$

$1 \le l \le r \le n$