题目描述

你有一张 $n$ 个结点，$m$ 条边的有点权，无边权的无向图。对于每一个 $1\le x\le n$，回答是否存在一条从 $1$ 到 $x$ 的路径，使得路径上的点权下凸。

称一个序列 $a_1,\ldots, a_k$ 是下凸的，当且仅当对任意 $2\le i<k$，$a_{i-1}+a_{i+1}\ge 2a_i$。

输入格式

输入的第一行有两个正整数 $n,m$，表示图的点数和边数。

第二行有 $n$ 个自然数 $h_1,h_2,\ldots,h_n$，依次表示所有点的点权。

之后有 $m$ 行，每行有两个正整数 $u,v$，表示一条边。

输出格式

输出一行 $n$ 个正整数，其中如果存在从 $1$ 到 $x$ 的下凸路径则第 $x$ 个正整数为 $1$，否则为 $0$。

样例 #1

样例输入 #1

4 4
6 5 0 9
1 2
2 3
3 4
4 2

样例输出 #1

1 1 0 1

提示

【样例解释】

$1\to 1$ 的路径点权序列为 $6$，下凸。

$1\to 2$ 的路径点权序列为 $6,5$，下凸。

$1\to 2\to 3$ 的点权序列为 $6,5,0$，其中 $6+0<2\times 5$，所以不下凸。

$1\to 2\to 4\to 3$ 的点权序列为 $6,5,9,0$，其中 $5+0<2\times 9$，所以不下凸。

$1\to 2\to 4$ 的点权序列为 $6,5,9$，其中 $6+9\ge 2\times 5$，所以下凸。

【数据范围】

对于全体数据，保证 $1\le n\le 2\times 10^5$，$1\le m\le 5\times 10^5$，$0\le h_i\le 10^{18}$。