#P18262. Frogs

Frogs

Frogs

在一片很长、很窄的池塘里,青蛙妈妈产下了 nn 个卵,第 ii 个卵位于位置 aia_i。青蛙按照 1,2,…,n1,2,\ldots,n 的顺序孵化。所有青蛙每次跳跃的长度均为 kk。

对于每个 p=2,3,…,np=2,3,\ldots,n,独立考虑前 pp 只青蛙玩追逐游戏的情况:第 ii 只追第 i+1i+1 只,最后一只(第 pp 只)追第1只。第 p+1p+1 至 nn 只不参与游戏。

游戏开始时,这些青蛙分别位于各自的初始位置 a1,…,apa_1,\ldots,a_p。此后每秒,所有参与的青蛙同时朝自己追逐的那只青蛙跳跃 kk 个单位:

  • 如果目标青蛙在右边,或者两只青蛙位置相同,就向右跳;
  • 否则向左跳。

形式化地,令第 pp 只的下一只为第1只。每秒根据这一秒开始时的位置,同时执行

$$a_i\gets\begin{cases}a_i+k,&a_{i+1}\ge a_i,\\a_i-k,&a_{i+1}<a_i.\end{cases}$$

青蛙妈妈担心孩子们离初始位置太远,最终跳出池塘。对于每个 pp,判断:如果游戏一直进行下去,是否会有至少一只参与的青蛙,在某个时刻距离它自己的初始位置至少

99(9999)99^{(99^{99})}

个单位。如果会,答案为1,否则为0。不同 pp 的游戏分别从初始位置开始,互不影响。

输入格式

第一行包含两个整数 n,kn,k。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

输出格式

输出一个长度为 n−1n-1 的01串,不含空格,依次表示 p=2,3,…,np=2,3,\ldots,n 的答案。

数据范围

  • 2≤n≤500 0002\le n\le500\,000;
  • 1≤k≤1091\le k\le10^9;
  • −109≤ai≤109-10^9\le a_i\le10^9;
  • 初始位置可以相同,输入只有一组数据。

样例

6 2
4 3 -3 5 100 100
01011

样例解释

当 p=2p=2 时,两只青蛙最初位于4和3,每两秒回到原位置,所以答案为0。下图为原题给出的最初几秒:

p=2 时的原题过程图

当 p=3p=3 时,初始位置为 [4,3,−3][4,3,-3],答案为1。下图显示最初几秒,之后会持续向左漂移:

p=3 时的原题过程图

当 p=4p=4 时,初始位置为 [4,3,−3,5][4,3,-3,5],答案为0。原题过程图如下:

p=4 时的原题过程图