BCS Mid Wales Programming Contest 2021

This challenge involves writing a simple cinema seat booking system.  Cinemas are opening up post lockdown, but they have to seat customers differently. No longer is it OK to try and fill all seats, or allow customers to choose their own.  

Each group who book through the booking office need to sit together, and there needs to be an empty seat between groups on all sides (left, right, infront and behind). The seats in the cinema are filled from the bottom left, in order of booking. If a row fills up, we start filling on the left hand side of the next row back.

(For the purposes of illustration, imagine that the screen is at the base of the grid and that we fill the front row first).

So, if we have a cinema with just three rows, with 10 seats per row, and the following group sizes in our booking

5 4 3 2 1

we will be able to seat the first group of 5 at bottom left, then the group of 4 next to them after a gap of one seat. We'll leave a row behind, then the back row will fit the 3, 2 and 1. The seats would look like this:

Seats:
1110110100
0000000000
1111101111

If there were more bookings and instead we had the group sizes

5 4 3 2 1 1 2 3 4 5

we would have to turn away some groups. In this case, the seats would look like this:

Seats:
1110110101
0000000000
1111101111
Failed to seat:
2
3
4
5

Input

The first line of your input contains two integers, which specify the size of the cinema in terms of number of rows and number of seats per row.

Output

Your output  should be the word "Seats:" on a line of its own, followed by an array of 1s and 0s represented the seats in the cinema (1=full, 0=empty). If you find that there are groups who cannot be seated in the cinema because it is too full, output the phrase "Failed to seat:" on the next line, followed by the sizes of the unseated groups in order, one per line.

Example

Input:
5 20
7 9 8 7 6 5 4 3 2 1 9 2 11 4 8

Output:
Seats:
11111101111101111000
00000000000000000000
11111111011111110000
00000000000000000000
11111110111111111000
Failed to seat:
3
2
1
9
2
11
4
8