Xoay vòng hoán vị

Cho một hoán vị $p$ độ dài $n$ và một mảng $a$ độ dài $m$ gồm các số nguyên từ $1$ đến $n$.

Bạn cần trả lời $q$ truy vấn, mỗi truy vấn có dạng: đoạn con của $a$ từ vị trí $l$ đến vị trí $r$ có chứa một dãy con là một phép xoay vòng của $p$ hay không?

Một phép xoay vòng của hoán vị $(p_1,p_2,\dots ,p_n)$ là hoán vị $(p_i,p_{i+1},\dots ,p_n,p_1,p_2,\dots ,p_{i-1})$ với $i$ nào đó từ $1$ đến $n$. Ví dụ hoán vị $(2,1,3)$ có ba phép xoay vòng: $(2,1,3)$, $(1,3,2)$ và $(3,2,1)$.

Dãy con của đoạn $a_l,\dots ,a_r$ là dãy $a_{i_1},a_{i_2},\dots ,a_{i_k}$ với $l\le i_1<i_2<\dots <i_k\le r$.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $q$.
• Dòng thứ hai chứa $n$ số nguyên: hoán vị $p$.
• Dòng thứ ba chứa $m$ số nguyên từ $1$ đến $n$: mảng $a$.
• $q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l_i$, $r_i$ ($1\le l_i\le r_i\le m$) mô tả một truy vấn.

Dữ liệu ra

In ra một xâu độ dài $q$ gồm các ký tự 0 và 1: ký tự thứ $i$ là 1 nếu đoạn từ vị trí $l_i$ đến $r_i$ của $a$ chứa một dãy con là phép xoay vòng của $p$, ngược lại là 0.

Ràng buộc

• $1\le n,m,q\le 2·{10}^5$

Ví dụ