← 返回题目列表

AtCoder · abc146_f

F. 双六

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

高桥正在玩一款名为“双六”的棋盘游戏。

板上有 N + 1 编号的方块 0 to N。高桥从 Square 开始 0,他必须正好停在 Square N 赢得比赛。

该游戏使用轮盘赌 M 号码来自 1 to M。在每一轮中,高桥都会旋转轮盘赌。如果数量 当他在 Square 时出现 x 当他在 Square 时出现 s,他移至 Square s+x。如果这能让他超越 Square N,他输了比赛。

此外,一些方块是游戏结束方块。如果他停在其中一个格子上,他也会输掉比赛。给你一个字符串 S 长度 N + 1,代表哪些方格是游戏结束方格。对于每个 i (0 \leq i \leq N),方形 i 是一个游戏结束方块,如果 S[i] = 1 而不是如果 S[i] = 0.

找出轮盘赌中出现的数字序列,其中高桥可以在尽可能少的回合数内赢得游戏。如果有多个这样的序列,找到字典顺序最小的这样的序列。如果高桥无法赢得比赛,则打印 -1.

约束

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • |S| = N + 1
  • S 包括 0 和 1.
  • S[0] = 0
  • S[N] = 0

输入

输入由标准输入按以下格式给出:

N M
S

输出

如果高桥能够赢得比赛,则打印高桥能够赢得比赛的轮盘赌中出现的最短数字序列中按字典顺序排列的最小序列,中间有空格。

如果 Takahashi 无法赢得比赛,则打印 -1.


示例输入 1

9 3
0001000100

示例输出 1

1 3 2 3

如果数字 1, 3, 2, 3 按这个顺序出现,高桥可以到达广场 9 通过广场 1, 4,和 6。他无法到达 Square 9 在三轮或更少的回合内,这是他到达 Square 的字典顺序最小的序列 9 四回合。


示例输入 2

5 4
011110

示例输出 2

-1

高桥无法到达广场 5.


示例输入 3

6 6
0101010

示例输出 3

6