ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural Championship 2008

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. Decimation

Time limit: 0.5 second
Memory limit: 64 MB
Decimation was a form of extreme military discipline used
in the Roman Army, when every tenth soldier was executed.
Do you think it is easy to work as a conductor in a tram? Persistent fare dodgers always try to ride free of charge, and ticket inspectors fine without remorse not only fare dodgers but also tram conductors because they don't cope with their duties.
In the course of operation Fare Dodger 2008, which was carried out recently by the Yekaterinburg Association of Ticket Inspectors, it turned out that in every tram there was at least one fare dodger at the moment of inspection. Chief Ticket Inspector of Yekaterinburg became furious and decided to punish conductors. He ordered to line them up in a column and to fine every tenth conductor a sum equal to an average conductor's salary.
Chief Fare Dodger of Yekaterinburg felt sorry for poor conductors and decided to help them, because he knew that some of the conductors were good and coped with their duties. Before conductors are fined, Chief Fare Dodger can place into the column some of his friends, who are also fare dodgers. Chief Ticket Inspector doesn't suspect this and will fine every person whose number in the column is a multiple of 10 (the number of the first person in the column is 1). Help Chief Fare Dodger to place his friends in the column so that the total number of fined fare dodgers and good conductors be minimal.

Input

The first line contains integers n (1 ≤ n ≤ 10000) and k (0 ≤ k ≤ 50) separated by a space; they are the number of conductors in the column and the number of Chief Fare Dodger's friends who are ready to help the conductors. The second line consists of n symbols; the ith symbol is “1” if the ith place in the column is initially occupied by a good conductor, and “0” if the conductor is bad.

Output

In the first line, output the minimal total number of fined fare dodgers and good conductors. In the second line, output the number m of fare dodgers that should be placed in the column, and then output m integers, which are their numbers in the resulting column. The numbers must be separated by a space.

Samples

inputoutput
10 2
0000000001
0
2 5 12
10 2
1111111111
1
0
Problem Author: Alexander Ipatov (idea — Stanislav Vasilyev)
Problem Source: The 12th Urals Collegiate Programing Championship, March 29, 2008
To submit the solution for this problem go to the Problem set: 1611. Decimation