Q3: Lecture Hall Dan holds his CSC108 lectures in a rectangular N X M lecture hall. In other words, this lecture hall has N rows of seats, each of them containing exactly M seats. Here's my attempt at drawing this layout when N = 3 and M = 5: Dan Off 00 lecture hall layout with 3 rows and 5 seats per row The rows are numbered from 1 to N starting from the front row. Similarly, the columns are numbered from 1 to M starting from the leftmost column. We write (r, c) to denote the c-th seat in the r-th row. When Dan walks into the lecture hall this morning, some of the seats are already taken (this is the initial layout of the lecture hall). After that, the students come in one group at a time. From experience, Dan knows that when a group of K students enter the lecture hall, they look for K consecutive empty seats. That is, they try to find an empty seat (r, c) such that for all integers i in [0, K-1], the seat (r, c + 1) exists and is empty. If they can't find K consecutive empty seats, they leave the lecture hall disappointedly and go play frisbee instead. Otherwise, they try to minimizer (if they have multiple options). If there are still multiple options with the minimum r, they try to minimize c. Note that with this description, one can always uniquely determine the seats they'll take given the layout of the seats and K. Moreover, Dan observes that sometimes students that are already seated may get up and leave the lecture hall (maybe they were in the wrong class or Dan was putting them to sleep). As you can imagine, it's distracting and noisy to have students walking around the lecture hall trying to find empty seats. Hence, as usual, Dan seeks to automate the process. Write a program that given the initial layout of the lecture hall and a description of the above-mentioned events in the order they happen, reports where every group entering the lecture hall should take their seats.Input The first line of the input contains two space-separated integers N and M denoting the number of rows and columns of the seat layout. The initial layout of the seats is described in the next N lines. Each line contains a string of length M and describes a single row of seats. The front row is described by the first line, the second row is described by the second line, and so on. The j-th seat in the i-th row is initially occupied if the j-th character of the i-th line is 1 and not occupied if the character is 0. The next line contains a single integer q, denoting the number of events. The events themselves are described in the following a lines in chronological order. Each line describes a single event. If the event corresponds to K students entering the hall, the line consists of the string in followed by the integer K. Otherwise, the line consists of the string out followed by two integers r and c; this indicates that the student sitting at (r, c) leaves the lecture hall. It's guaranteed that there exists a student sitting there before this event. Output For every group of K students entering the lecture hall, report on a single line which seats they take. If they can't find к consecutive empty seats, print -1. Otherwise, if they take the seats (r, c + i) for i in [0, K-1]), printr c. Report these in the order they happen. At the end of the output, print the final layout of the seats in the same format as the input. Sample Input 1 34 0110 0001 1010 6 in 3 out 2 2 in 2 in 1 out 2 3 in 2 Sample Output 1 21 -1 11 22 1110 1111 1010