Create Array Generator Service

At each step, pick any currently available element (repeats allowed) and append it to the result; then every position that is 0 and whose left neighbor was originally 1 becomes 1 simultaneously. Unlocking does not depend on what was picked and spreads only one cell to the right. Perform m steps and maximize the result lexicographically. When everything is 0 and nothing can be picked, this site's standard I/O convention is to output -1.

输入格式

The first line contains n m, the second line contains n positive integers, and the third line contains a 01 availability string. This site sets 1≤n,m≤100000, elements in 1..10⁹, and a string length of n.

输出格式

If there is no solution, output -1; otherwise output the m chosen values.

样例 1

输入：

4 2
10 5 7 6
0101

输出：

6 7

样例 2

输入：

5 4
4 9 1 2 10
10010

输出：

4 10 10 10

样例 3

输入：

2 3
2 9
00

输出：

-1

样例说明

Example 1: initially 5 and 6 are available, so take 6 first; after 7 is unlocked, take 7. Example 2: take 4 first; after one round both 9 and 10 are unlocked, and every later pick is 10, so output 4 10 10 10, correcting the source's 4 9 10 10. Example 3: no element is initially available, so there is no solution; output -1.