题目描述

有 $n$ 个点，每个点有点权 $a_1\sim a_n$。若 $a_i \& a_j=0$（指二进制下按位与），则在 $i,j$ 间连一条边权为 $1$ 的边。

求 $S$ 到 $1\sim n$ 的最短路。

输入格式

第一行两个正整数 $n,S$。

接下来一行 $n$ 个非负整数，第 $i$ 个为 $a_i$。

输出格式

一行 $n$ 个整数，第 $i$ 个为 $S$ 到 $i$ 的最短路长度。不能到达输出 -1。

样例

样例输入

5 3
2 3 4 5 6

样例输出

1 1 0 2 -1

样例解释

连了 $(1,3),(2,3),(1,4)$ 三条边。

数据范围

对于所有数据，$1\le n\le 10^5$，$0\le a_i\le 131071$。