在一个非常长且狭窄的池塘里，青蛙妈妈产下了 $n$ 枚卵，第 $i$ 枚卵位于位置 $a_i$。从每枚卵中，青蛙按 $1$ 到 $n$ 的顺序孵化（出生）。同时给定跳跃长度 $k$。

在某个时刻，前 $p$ 只孵化的青蛙将开始玩“青蛙捉人”游戏。在这个游戏中，每只青蛙都在无限地追逐它的弟弟妹妹，而最年轻的青蛙追逐最年长的青蛙（青蛙 $i$ 追逐青蛙 $i+1$，青蛙 $p$ 追逐青蛙 $1$）。每一秒，每只青蛙都会朝着它正在追逐的青蛙的方向跳跃 $k$ 个单位（向左或向右）；如果它们处于同一位置，则向右跳。第 $p+1$ 到 $n$ 只青蛙不参与游戏。形式化地，对于 $p$ 只青蛙中的每一只，同时进行以下操作：如果 $a_{1+(i \pmod p)} \ge a_i$，则 $a_i$ 增加 $k$，否则 $a_i$ 减少 $k$。

青蛙妈妈担心她的孩子们可能会跑得太远而跳出池塘。对于每个 $p$ 从 $2$ 到 $n$，独立地检查在包含青蛙 $1, 2, \dots, p$ 的“青蛙捉人”游戏中，是否会有任何一只青蛙偏离其初始位置至少 $99^{(99^{99})}$。如果发生这种情况，对于每个 $p$ 输出 $1$，否则输出 $0$。

输入格式

第一行包含两个整数 $n$ 和 $k$ ($2 \le n \le 500\,000; 1 \le k \le 10^9$)，分别表示卵的数量和跳跃长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$)，表示卵的位置。

输出格式

输出每个 $p = 2, 3, \dots, n$ 对应的答案，中间不要有空格。如果前 $p$ 只青蛙无限期地进行游戏，且其中任何一只青蛙偏离其初始位置至少 $99^{(99^{99})}$，则输出 $1$，否则输出 $0$。因此，输出应该是一个长度为 $n-1$ 的二进制字符串。

样例

输入 1

6 2
4 3 -3 5 100 100

输出 1

01011

说明

下图（参见后续页面）展示了 $p=2, 3, 4$ 时“青蛙捉人”游戏最初几秒的情况。 对于 $p=2$，两只青蛙分别从位置 $4$ 和 $3$ 开始，它们每 $2$ 秒回到初始位置。没有青蛙偏离其起始位置太远，因此答案为 $0$。

对于 $p=3$，初始位置为 $a = [4, 3, -3]$。答案为 $1$。

对于 $p=4$，初始位置为 $a = [4, 3, -3, 5]$。答案为 $0$。