题目描述

There is a field consisting of $N$ cells in a row, numbered $0$ to $N-1$ from left to right. Each cell has a distinct height: the height of cell $i$ is $p_i$, and the sequence $p_0,p_1,\ldots,p_{N-1}$ is a permutation of the numbers $0,1,\ldots,N-1$.

Two cells with indices $i$ and $j$ are called close if and only if $|i-j|\le 1$. In particular, every cell is close to itself.

A robot stands on the field, initially placed at some cell. The robot accepts commands of the following two types:

• MAX: among all cells close to the robot's current cell, its next position is the unique cell with the maximum height;
• MIN: among all cells close to the robot's current cell, its next position is the unique cell with the minimum height.

Since a cell is close to itself, a command may leave the robot at the same cell.

A program is a finite sequence of commands, where every command is either MAX or MIN. If the robot starts at cell $X$ and follows program $S$, it ends at a uniquely determined cell, denoted by $\operatorname{result}(S,X)$.

You will be asked $Q$ queries. The $i$-th query gives a set of $K_i$ starting cells $x_0,x_1,\ldots,x_{K_i-1}$. The robot will be placed at one of them, but which one is not known in advance. For each query, determine whether there is a program that moves the robot to the same final cell regardless of the chosen starting position.

Formally, determine whether there exists a program $S$ such that

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

The permutation $p$ is the same for all queries.

You do not need to construct such a program; only report whether one exists.

Implementation details

Implement the following two functions:

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

• $p$: a permutation of the numbers from $0$ to $N-1$.

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

• $x$: the cells for one query, given in strictly increasing order.

initialize is called exactly once, before any calls to exists_program.

exists_program is called $Q$ times, once for each query. It must return true if there exists a program after which the robot ends at the same cell no matter which given cell it started from, and false otherwise.

输入格式

Input format:

• line $1$: two integers $N$ and $Q$;
• line $2$: $N$ integers $p_0,p_1,\ldots,p_{N-1}$, where $p_i$ is the height of cell $i$;
• line $3+i$: an integer $K_i$, followed by $K_i$ integers $x_0,x_1,\ldots,x_{K_i-1}$ describing the $i$-th query.

输出格式

Output format:

• line $1$: a binary string of length $Q$ whose $i$-th character is 1 if the answer to query $i$ is true, and 0 otherwise.

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

提示

Explanation of example 1

Here $p=[0,2,1]$. For the second query, the robot may start at cell $0$, $1$, or $2$. Consider the program $[\texttt{MAX}]$.

• Starting at cell $0$, the close cells are $0$ and $1$. Since $p_0<p_1$, the robot moves to cell $1$.
• Starting at cell $1$, the close cells are $0$, $1$, and $2$. Since $p_0<p_1$ and $p_1>p_2$, the robot stays at cell $1$.
• Starting at cell $2$, the close cells are $1$ and $2$. Since $p_1>p_2$, the robot moves to cell $1$.

Thus a program exists that ends at cell $1$ from all three starting cells, so the answer is true. Other valid programs include $[\texttt{MIN},\texttt{MAX}]$, $[\texttt{MIN},\texttt{MIN},\texttt{MAX},\texttt{MIN},\texttt{MAX},\texttt{MIN}]$, and $[\texttt{MAX},\texttt{MIN},\texttt{MAX}]$.

Explanation of example 2

Here $p=[0,4,2,1,3,5,6]$.

For the first two queries, no program can make the robot end at the same cell from every given starting cell, so both answers are false.

For the last query, the robot may start at cell $3$ or $6$. Consider $[\texttt{MAX},\texttt{MAX},\texttt{MAX}]$.

• Starting at cell $3$, the close cells are $2$, $3$, and $4$. Since $p_3<p_4$ and $p_2<p_4$, the robot moves to cell $4$. Applying the next two commands similarly, it ends at cell $6$.
• Starting at cell $6$, it remains at cell $6$ throughout.

Therefore the answer is true. The program $[\texttt{MIN},\texttt{MAX},\texttt{MAX},\texttt{MAX}]$ also works. In contrast, $[\texttt{MAX},\texttt{MAX}]$ ends at cell $5$ from cell $3$, but at cell $6$ from cell $6$.

Constraints

• $3\le N\le 2\cdot 10^5$
• $1\le Q\le 5\cdot 10^5$
• $p_0,p_1,\ldots,p_{N-1}$ is a permutation of $0,1,\ldots,N-1$
• $2\le K_i\le N$
• $0\le x_0<x_1<\cdots<x_{K_i-1}<N$ for every query
• The sum of $K_i$ over all $Q$ queries does not exceed $10^6$

Subtasks

Subtask	Points	$N$	$Q$	$K_i$	Additional constraints
0		-			The examples.
1	3	$\le 2\cdot 10^5$	$\le 5\cdot 10^5$	$=2$	If the answer is positive, a valid program using exactly $1$ command exists.
2	7				If the answer is positive, a valid program using at most $5$ commands exists.
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$ for every query.
6	8	$\le 5000$		$\le N$	-
7	13	$\le 2\cdot 10^5$			There exist $0<a<b<N-1$ such that $p_0<p_1<\cdots<p_a>p_{a+1}>\cdots>p_b<p_{b+1}<\cdots<p_{N-1}$.
8					$p_0<p_1>p_2<p_3>\cdots<p_{N-1}$ if $N$ is even; $p_0<p_1>p_2<p_3>\cdots>p_{N-1}$ if $N$ is odd.
9	23				-