题目描述

有一片由 $N$ 个格子排成一行的场地，从左到右编号为 $0$ 到 $N-1$。每个格子的高度互不相同：格子 $i$ 的高度为 $p_i$，序列 $p_0,p_1,\ldots,p_{N-1}$ 是 $0,1,\ldots,N-1$ 的一个排列。

当且仅当 $|i-j|\le 1$ 时，编号为 $i$ 和 $j$ 的两个格子称为接近的。特别地，每个格子都与自身接近。

一个机器人站在场地上，初始位于某个格子。机器人可以接受以下两类命令：

• MAX：在与机器人当前格子接近的所有格子中，机器人下一步将位于高度最大的唯一格子；
• MIN：在与机器人当前格子接近的所有格子中，机器人下一步将位于高度最小的唯一格子。

由于格子与自身接近，一条命令执行后机器人可能仍停在原地。

一个程序是由有限条命令组成的序列，其中每条命令均为 MAX 或 MIN。若机器人从格子 $X$ 出发并执行程序 $S$，它将停在一个唯一确定的格子，记为 $\operatorname{result}(S,X)$。

你需要回答 $Q$ 次询问。第 $i$ 次询问给出一个由 $K_i$ 个起始格子 $x_0,x_1,\ldots,x_{K_i-1}$ 组成的集合。机器人会被放在其中某个格子上，但具体是哪一个事先未知。对于每次询问，请判断是否存在一个程序，使得无论选中哪个起始格子，机器人最终都会到达同一个格子。

形式化地，你需要判断是否存在程序 $S$，满足

$$\operatorname{result}(S,x_0)=\operatorname{result}(S,x_1)=\cdots=\operatorname{result}(S,x_{K_i-1}).$$

所有询问使用同一个排列 $p$。

你不需要构造这样的程序，只需报告它是否存在。

实现细节

你需要实现以下两个函数：

void initialize(std::vector<int> p)

• $p$：$0$ 到 $N-1$ 的一个排列。

bool exists_program(std::vector<int> x)

• $x$：一次询问给出的格子，按严格递增顺序排列。

函数 initialize 恰好调用一次，并且发生在所有 exists_program 调用之前。

函数 exists_program 共调用 $Q$ 次，每次询问调用一次。如果存在某个程序，使得机器人无论从给定的哪个格子出发，最终都会停在同一个格子，则应返回 true；否则返回 false。

输入格式

输入格式：

• 第 $1$ 行：两个整数 $N$ 和 $Q$；
• 第 $2$ 行：$N$ 个整数 $p_0,p_1,\ldots,p_{N-1}$，其中 $p_i$ 表示格子 $i$ 的高度；
• 第 $3+i$ 行：一个整数 $K_i$，随后是 $K_i$ 个整数 $x_0,x_1,\ldots,x_{K_i-1}$，描述第 $i$ 次询问。

输出格式

输出格式：

• 第 $1$ 行：一个长度为 $Q$ 的二进制串。若第 $i$ 次询问的答案为 true，则第 $i$ 个字符为 1，否则为 0。

3 3
0 2 1
2 0 2
3 0 1 2
2 1 2

111

7 3
0 4 2 1 3 5 6
3 0 1 3
3 1 3 4
2 3 6

001

提示

样例 1 解释

本例中 $p=[0,2,1]$。对于第二次询问，机器人可能从格子 $0$、$1$ 或 $2$ 出发。考虑程序 $[\texttt{MAX}]$。

• 若从格子 $0$ 出发，与其接近的是格子 $0$ 和 $1$。由于 $p_0<p_1$，机器人移动到格子 $1$。
• 若从格子 $1$ 出发，与其接近的是格子 $0$、$1$ 和 $2$。由于 $p_0<p_1$ 且 $p_1>p_2$，机器人停在格子 $1$。
• 若从格子 $2$ 出发，与其接近的是格子 $1$ 和 $2$。由于 $p_1>p_2$，机器人移动到格子 $1$。

因此存在一个程序，使机器人从三个起点出发最终都停在格子 $1$，答案为 true。其他可行程序包括 $[\texttt{MIN},\texttt{MAX}]$、$[\texttt{MIN},\texttt{MIN},\texttt{MAX},\texttt{MIN},\texttt{MAX},\texttt{MIN}]$ 和 $[\texttt{MAX},\texttt{MIN},\texttt{MAX}]$。

样例 2 解释

本例中 $p=[0,4,2,1,3,5,6]$。

对于前两次询问，不存在能让机器人从所有给定起点出发后停在同一格子的程序，因此两个答案均为 false。

对于最后一次询问，机器人可能从格子 $3$ 或 $6$ 出发。考虑程序 $[\texttt{MAX},\texttt{MAX},\texttt{MAX}]$。

• 若从格子 $3$ 出发，与其接近的是格子 $2$、$3$ 和 $4$。由于 $p_3<p_4$ 且 $p_2<p_4$，机器人移动到格子 $4$。类似地执行接下来的两条命令后，它最终到达格子 $6$。
• 若从格子 $6$ 出发，它会一直停在格子 $6$。

因此答案为 true。程序 $[\texttt{MIN},\texttt{MAX},\texttt{MAX},\texttt{MAX}]$ 也可行。相反，程序 $[\texttt{MAX},\texttt{MAX}]$ 从格子 $3$ 出发时会停在格子 $5$，从格子 $6$ 出发时则停在格子 $6$。

限制

• $3\le N\le 2\cdot 10^5$
• $1\le Q\le 5\cdot 10^5$
• $p_0,p_1,\ldots,p_{N-1}$ 是 $0,1,\ldots,N-1$ 的一个排列
• $2\le K_i\le N$
• 对每次询问均有 $0\le x_0<x_1<\cdots<x_{K_i-1}<N$
• 所有 $Q$ 次询问中 $K_i$ 的总和不超过 $10^6$

子任务

子任务	分值	$N$	$Q$	$K_i$	附加限制
0		-			样例。
1	3	$\le 2\cdot 10^5$	$\le 5\cdot 10^5$	$=2$	若答案为肯定，则存在恰好使用 $1$ 条命令的可行程序。
2	7				若答案为肯定，则存在至多使用 $5$ 条命令的可行程序。
3	9	$\le 100$	$\le 500$		-
4	17	$\le 5000$	$\le 5\cdot 10^5$
5	7	$\le 2\cdot 10^5$			每次询问均有 $x_1=x_0+1$。
6	8	$\le 5000$		$\le N$	-
7	13	$\le 2\cdot 10^5$			存在 $0<a<b<N-1$，使得 $p_0<p_1<\cdots<p_a>p_{a+1}>\cdots>p_b<p_{b+1}<\cdots<p_{N-1}$。
8					若 $N$ 为偶数，则 $p_0<p_1>p_2<p_3>\cdots<p_{N-1}$；若 $N$ 为奇数，则 $p_0<p_1>p_2<p_3>\cdots>p_{N-1}$。
9	23				-