题目描述

有 $n$ 个点，第 $i$ 个点的权值为 $a_i$。
现在按照如下规则制定一种行走方案：

• 若当前处在点 $i$，如果 $a_i=a_j$，则可以从点 $i$ 直接传送到点 $j$。
• 若当前处在点 $i$，如果 $gcd(a_i,a_j)\ne 1$，则可以花费 $1$ 个金币从点 $i$ 走到点 $j$。
• 若当前处在点 $i$，如果 $a_i\oplus a_j\le k$，则可以花费 $1$ 个金币从点 $i$ 走到点 $j$。

$gcd(x,y)$ 表示 $x$ 和 $y$ 的最大公约数，$x\oplus y$ 表示 $x$ 按位异或 $y$ 的结果。

现在问你从第 $s$ 个点出发，分别走到点 $1\sim n$ 最少需要花费多少金币？

输入格式

第一行三个整数 $n,k,s$。
第二行 $n$ 个整数，表示 $a_1\sim a_n$。

输出格式

一行 $n$ 个整数，分别表示走到点 $1\sim n$ 最少需要花费的金币数量，如果无法到达，输出 $-1$。

输入输出样例 #1

输入 #1

5 2 1
1 2 3 4 5

输出 #1

0 2 1 3 4

说明/提示

$1\le n\le 2\times 10^5,0\le k\le 5,1\le s\le n,1\le a_i\le 10^6$