青蛙跳跃问题

题目解析

这个问题要求我们判断青蛙在执行一系列包含确定指令（L、R）和不确定指令（?）后可能停留的位置。关键在于处理不确定指令的所有可能性，确定最终青蛙可能到达的所有位置。

解题思路

考虑到指令"?"可以是L或R，如果有多个"?"指令，我们需要考虑这些指令所有可能的组合。直接枚举所有可能性会导致指数级复杂度，这对于长度达10^6的指令序列是不可行的。

题目内容

小美有一个一维的坐标系，上面一共有$n$个点，依次为$1,2,...,n$，她有一只遥控青蛙，初始时位于$k$。现在，她在纸上书写了一个指令集:

• 指令$L$:指挥青蛙向左移动一个单位，如果当前位于$1$，则原地不动。
• 指令$R$:指挥青蛙向右移动一个单位，如果当前位于$n$，则原地不动。
• 指令$?$:未知，随机变成$L$或者$R$，并指挥青蛙移动。

对于指令$?$的全部可能取值，小美想知道青蛙最终有概率停在哪些位置。如果该点可能成为终点，输出$1$，否则输出$0$

输入描述

第一行输入两个整数$n,k(1≤n≤10^6;1≤k≤n)$分别表示坐标系长度和青娃的初始位置。

第二行输入一个长度不超过$10^6$且仅由$L,R$和$?$构成的字符串$S$，表示移动的指令集。

输出描述

在一行上输出 $n$个数字$a_1,a_2,...,a_n(0≤a_i≤1)$代表

每一个点是否可能成为青蛙的终点，数字之间不必使用空格隔开。

样例1

输入

3 2
RL?

输出

101

说明

青蛙会先向右一格到达$3$，随后向左一格回到$2$；由于第三个指令是$?$，小红有可能指挥青蛙向左到达1，也有可能向右到达$3$。

样例2

输入

5 2
?????

输出

11111