Students often have problems taking up seats. When two students want the same seat, a quarrel will probably begin.
It will have very bad effect when such subjects occur on the BBS.
So, we urgently need a seat-taking-up rule. After several days of argument, the rule finally comes out:
As shown in the figure below, the seats in a classroom form a n×m grid( n rows and m columns), and every cell in the grid represents a seat. The coordinates of the seat in the north-west corner are (1,1) and the coordinates of the seat in the south-east corner seat are (n,m). As you know, some seats make you feel good and some seats don’t. So every seat has a “feeling index”.
Students can take up seats for himself and his friends. Of course, if a seat is already taken up by a student, it can’t be taken up by others.
For the convenience of communication between friends, when a student is trying to take up seats, he wants all the seats he needs to be consecutive and in the same row. If he can do that, he takes up all the seats he needs, and save the most western one for himself. For example, if a student wants to take up 3 seats, then taking (2,2),(2,3),(2,4) and saving (2,2) for himself is ok; but taking (2,2),(2,4),(2,5) is invalid because those seats are not consecutive. Under the precondition of accomplishing his seat-taking job, a student always wants the “feeling index” of his seat to be as large as possible.
However, if a student cannot take up all the seats he needs, he will just try to take up only one seat for himself because he doesn’t want to get into the trouble of explaining “Why they can get seats but I can’t?” to some of his friends. Of course he still wants the “feeling index” of his seat to be as large as possible in that situation.
Everyone wants to know where are the seats he can take up .This problem seems a little bit complicated for them. So they want you to write a program to solve the problem.