题目描述

文景随手写出了 \(1 \sim n\) 的一个排列 \(p=\{p[1],…,p[i],…,p[n]\}（1≤n≤2×10^5）\)，缠着妈妈给他出题。

妈妈也随手写出了一个序列 \(a=\{a[1],…,a[i],…,a[m]\}（1≤a[i]≤n）\)，长度为 \(m（1≤m≤2×10^5）\)。

妈妈给出了 \(q\) 次询问，每次询问给定 \(l\) 和 \(r\)，询问 \([l,r]\) 区间，能否找到一个子序列等于排列 \(p\) 的某个循环移位序列。

\(p\) 的循环移位序列：

例如 \(p\) 循环左移 \(i\) 次，可以得到 \(\{p[i+1],…,p[n],p[1],…,p[i]\}\)。

格式

输入格式

第一行三个正整数 \(n,m,q（1≤n,m,q≤2×10^5）\)，用空格隔开；

第二行 \(n\) 个正整数，表示文景随手写的排列 \(p\)，以空格隔开；

第三行 \(m\) 个正整数，表示妈妈随手写的 \(a\) 序列，以空格隔开；

以下 \(q\) 行，每行两个正整数 \(l\) 和 \(r\)，表示一个询问。

输出格式

对于所有的询问输出在一行。

对于每个询问用 \(1\) 表示可以在 \([l,r]\) 区间，找到一个子序列等于排列 \(p\) 的某个循环移位序列；用 \(0\) 表示无法找到；

每个询问的回答之间不用输出空格。

样例1

样例输入1

3 6 3
2 1 3
1 2 3 1 2 3
1 5
2 6
3 5

样例输出1

110

样例解释

\([1,5]\) 区间，可以找到 \(\{1,3,2\}\)；

\([2,6]\) 区间，可以找到 \(\{2,1,3\}\)；

\([3,5]\) 区间，找不到；

限制

时间：\(1s\) 空间：\(256M\)

对于 \(20\%\) 的数据：\(1≤n,m,q≤100\)；

对于 \(50\%\) 的数据：\(1≤n,m,q≤500\)；

对于 \(100\%\) 的数据：\(1≤n,m,q≤2×10^5\)；

来源

地址：\(zloj,J2021\)域
作者：\(jialiang2509\)