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\)