这里提供一种时间复杂度为 $O(N + M)$ 的做法： 观察到，dp数组有且仅有 00000111110101011111000 这种前缀连续 1 中间可能有 01 交错段后缀连续 1 的情况，考虑存储 dp 数组内 1 出现的第一个位置和最后一个位置，被 1 完全包含的 0 出现的第一个位置和最后一个位置，发现可以使用这些信息直接转移。

#include <bits/stdc++.h>

using namespace std;

int n;

题目内容

小红有一个一维的坐标系，上面一共有$n$个点，依次为$1,2,…,n$，他初始时位于$k$。现在她按照一个指令集合运动，如下:

·指令$L$:向左移动一个单位，如果当前位于$1$，则原地不动。

·指令$R$:向右移动一个单位，如果当前位于$n$，则原地不动。

·指令$?$:未知，小红将随机移动$L$或者$R$。

在经过所有指令运动后，小红想知道哪些位置有可能成为终点。

如果该点可能成为终点，输出$1$，否则输出$0$。

输入描述

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

第二行输入一个长度不超过$10^5$且仅由$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