All cinema halls in Berland are rectangles with K rows of K seats each, and K is an odd…
- User
All cinema halls in Berland are rectangles with K rows of K seats each, and K is an odd number. Rows and seats are numbered from 1 to K. For safety reasons people, who come to the box office to buy tickets, are not allowed to choose seats themselves. Formerly the choice was made by a cashier, but now this is the responsibility of a special seating program. It was found out that the large majority of Berland's inhabitants go to the cinema in order to watch a movie, that's why they want to sit as close to the hall center as possible. Moreover, a company of M people, who come to watch a movie, want necessarily to occupy M successive seats in one row. Let's formulate the algorithm, according to which the program chooses seats and sells tickets. As the request for M seats comes, the program should determine the row number x and the segment [yl, yr] of the seats numbers in this row, where yr - yl + 1 = M. From all such possible variants as a final result the program should choose the one with the minimum function value of total seats remoteness from the center. Say, — the row and the seat numbers of the most "central" seat. Then the function value of seats remoteness from the hall center is . If the amount of minimum function values is more than one, the program should choose the one that is closer to the screen (i.e. the row number x is lower). If the variants are still multiple, it should choose the one with the minimum yl. If you did not get yet, your task is to simulate the work of this program. Input
The first line contains two integers N and K (1 ≤ N ≤ 1000, 1 ≤ K ≤ 99) — the amount of requests and the hall size respectively. The second line contains N space-separated integers Mi from the range [1, K] — requests to the program.
Output
Output N lines. In the i-th line output «-1» (without quotes), if it is impossible to find Mi successive seats in one row, otherwise output three numbers x, yl, yr. Separate the numbers with a space.
Examples
Input
2 1 1 1
Output
1 1 1 -1
Input
4 3 1 2 3 1
Output
2 2 2 1 1 2 3 1 3 2 1 1
Assistant
We are given a problem: There is a cinema hall with K rows of K seats each, K is odd. Rows and seats are numbered from 1 to K. For each request of M seats (M from 1 to K), we need to find a row x and a contiguous segment [yl, yr] (length M) such that all seats are free (initially all seats are free, and then once assigned they become occupied and cannot be used for subsequent requests). The selection algorithm: Among all possible placements (i.e., in any row where there exists a contiguous block of M free seats), we choose the one that minimizes the "total seats remoteness from the center". The center is defined as the seat at row c = (K+1)/2 and seat c (since K odd). The remoteness of a seat (x,y) from center is |x-c| + |y-c|? Actually: "the function value of seats remoteness from the hall center is ". The image likely shows sum over seats of (|x - c| + |y - c|). Or maybe it's sum of distances (Manhattan distance) from the center. Let's interpret: The problem says: "the function value of total seats remoteness from the center. Say, — the row and the seat numbers of the most 'central' seat. Then the function value of seats remoteness from the hall center is ." Possibly the function is sum_{i=1}^{M} (|x - c| + |y_i - c|) for all seats in the block. Or maybe it's something else. Usually in such problems (like "movie goers" or "cinema" from Codeforces) the cost is sum of distances from the center. Let's check examples.
Example 1: K=1. N=2, M1=1, M2=1. Center: (1,1). For first request, we have only one seat: row1 seat1. Its distance: |1-1|+|1-1|=0. So output "1 1 1". For second request, no free seats, output -1. That matches.
Example 2: K=3. N=4. M: 1,2,3,1. We need to simulate. Initially all seats free. K=3, center c=2 (since (3+1)/2=2). Compute distances: seat (i,j) distance d = |i-2|+|j-2|. Let's compute all: Row1: (1,1): | -1|+|-1|=2; (1,2):1+0? Actually |1-2|=1,|2-2|=0 =>1; (1,3):1+1=2. Row2: (2,1):0+1=1; (2,2):0+0=0; (2,3):0+1=1. Row3: (3,1):1+1=2; (3,2):1+0=1; (3,3):1+1=2.
Now first request M=1. We need to choose a free seat minimizing total remoteness (which is just d). The seats with minimum d: (2,2) d=0. So we would choose (2,2). Output should be "2 2 2". That matches example: first line output: 2 2 2.
Second request M=2. Now seat (2,2) is occupied. We need to find a row with a contiguous block of 2 free seats. Let's list possible blocks:
Row1: seats (1,1)-(1,2) and (1,2)-(1,3). But note (1,2) is free? All except (2,2) are free initially. So Row1 has both blocks possible: block starting at y=1 length 2: seats (1,1),(1,2); block starting at y=2: seats (1,2),(1,3). Row2: seats (2,1)-(2,2) contains occupied (2,2) so not free; (2,2)-(2,3) contains occupied (2,2) so not free. Row3: blocks (3,1)-(3,2) and (3,2)-(3,3) both free.
Now compute total remoteness for each block: sum of distances for seats in block.
For block (1,1)-(1,2): distances: (1,1)=2, (1,2)=1 => total=3. (1,2)-(1,3): (1,2)=1, (1,3)=2 => total=3. (3,1)-(3,2): (3,1)=2, (3,2)=1 => total=3. (3,2)-(3,3): (3,2)=1, (3,3)=2 => total=3.
All have total=3. So tie on remoteness. Then tie-breaking: choose the one with lower row number x. Among these blocks, rows are 1 and 3. So row1 lower. Among row1 blocks, we have two: yl=1 and yl=2. Need to choose the one with minimum yl? Actually: "If the amount of minimum function values is more than one, the program should choose the one that is closer to the screen (i.e. the row number x is lower). If the variants are still multiple, it should choose the one with the minimum yl." So among row1 blocks, we compare yl: yl=1 vs yl=2, choose yl=1. So final block: row1, seats 1-2. Output: "1 1 2". That matches example: second line "1 1 2". Good.
Third request M=3. Now occupied seats: (2,2) and (1,1),(1,2) (since we occupied row1 seats 1 and 2). Actually we occupied row1 seats 1 and 2? But note second request gave block (1,1)-(1,2) => seats (1,1) and (1,2) are now occupied. So current occupancy: row1: seats 1 and 2 occupied, seat3 free. Row2: seat2 occupied, seats1 and3 free. Row3: all free.
Now we need a contiguous block of 3 seats in one row. Only rows that have any block of length 3: only row3? Row1 only has seat3 free but block of length3 would require all three seats free, but seats1,2 are occupied so cannot. Row2: seat2 occupied so cannot have block of length3. Row3: all free, so block (3,1)-(3,3) is available. So we must choose row3 seats 1-3. Total remoteness sum = (3,1)=2, (3,2)=1, (3,3)=2 => total=5. So output: "3 1 3". That matches example: third line "3 1 3".
Fourth request M=1. Now occupied: row1:1,2; row2:2; row3:1,2,3. So free seats: row1:3; row2:1,3; row3: none? row3 all occupied. Which seat to choose for M=1? We need to minimize distance. Compute distances of free seats: (1,3):2; (2,1):1; (2,3):1. Minimum distance=1. Among those, there are two with distance 1: (2,1) and (2,3). Tie on remoteness (both total=1) -> choose lower row number? Both in row2, same row. Then choose lower yl? Since they are single seats, yl=yr=1 or 3. So choose min yl =1. So output: "2 1 1". Actually example output: "2 1 1". Yes, that matches. So our interpretation is correct.
Thus, we need to simulate N requests, each time selecting a contiguous block of length M in a row with all seats free, according to:
- Minimize total distance sum_{i=yl}^{yr} (|x - c| + |i - c|) where c = (K+1)/2.
- If ties, choose smallest row number x.
- If still ties (same row?), choose smallest yl.
The hall size K up to 99, which is small. N up to 1000, which is also small. Straightforward simulation: For each request, iterate over all rows (1..K) and over all possible starting columns (1..K-M+1) such that the segment of length M is fully free. Compute sum of distances. Pick best according to criteria. Then mark those seats as occupied.
Given K max 99, rows=99, columns=99, M up to K, so per request worst-case: O(K * K) = ~10^4, times N=1000 => 10^7, which is fine.
But careful: Need to compute distances efficiently? We can precompute distance matrix d[x][y] = |x-c| + |y-c|. Then sum for block = sum_{j=yl}^{yr} d[x][j]. For each row x and each start yl, we need sum over M consecutive seats. Could precompute prefix sums per row to get O(1) per block, but given K <= 99, even O(K) per block is fine: M max 99, rows 99, blocks per row ~ up to 99, so per request ~ 999999 ~ 10^6 worst-case? Actually if we compute sum by iterating M for each block, that would be O(K^3) per request (since for each row (K), for each start (K-M+1), iterate M seats). But K <= 99, K-M+1 approx up to 99, M up to 99, so that is ~ 99 * 99 * 99 = 970,299 per request, times 1000 = ~ 9.7e8, which might be borderline but likely okay in C++ but might be high in Python? However problem constraints: N <= 1000, K <= 99, worst-case about 1e9 operations. But many requests might be small? Not safe. Better to use prefix sums to compute block sum in O(1). But we can also optimize: For each row, we can precompute free segments, but simpler: Since K is very small (max 99), we can afford O(K^2 * something). Let's calculate more precisely: For each request, we need to consider all rows (K) and for each row, all possible start positions (<=K). That's up to 99*99=9801 blocks. For each block, we need to check if all seats are free: that would require checking M seats. If we check naively, that's 9801 * M (max 99) = ~970k per request. 1000 requests => 970 million checks. Each check is simple. In Python, 1e9 operations may be too slow. But we can reduce: we can maintain per row a boolean array of occupied seats. For each block, we need to test if the segment is free. Could precompute next free positions or use a segment tree? But K is small, maybe Python can handle if optimized? 970 million boolean checks might be ~10 seconds or more. Not ideal.
But we can precompute prefix sums for occupied seats: for each row, maintain an array of cumulative occupied count. Then we can check in O(1) if a block is free: if (occupied_prefix[yr] - occupied_prefix[yl-1] == 0). Also we need sum of distances: we can precompute distance prefix sums per row: dist_prefix[x][j] = sum_{i=1}^{j} d[x][i]. Then block sum = dist_prefix[x][yr] - dist_prefix[x][yl-1]. So per block, we do O(1) operations: compute sum, check free, then compare. That's 9801 blocks per request. 1000 * 9801 = 9.8 million, which is fine. However we still need to iterate all rows and all start positions. That's 9.8 million iterations, each with a few integer operations. That's perfectly fine in Python.
But we need to be careful about the tie-breaking: we compare (total_sum, row, start). So we can compute best = (min_total, best_row, best_yl). Initialize best_total = INF, best_row = INF, best_yl = INF. For each row x from 1..K, for yl from 1..K-M+1, yr = yl+M-1. Check if free: if occ_prefix[x][yr] - occ_prefix[x][yl-1] == 0. If free, compute sum = dist_prefix[x][yr] - dist_prefix[x][yl-1]. Then compare: if sum < best_total: update; elif sum == best_total and x < best_row: update; elif sum == best_total and x == best_row and yl < best_yl: update. At the end, if best_total still INF => no placement => print -1; else mark those seats as occupied (update occ array and occ_prefix for that row), and print best_row, best_yl, best_yr.
But we need to update occ_prefix after each marking: when we mark a block of seats as occupied, we can update the row's occupied array, and recompute prefix sums for that row (which is O(K) per row per request). Since K <= 99, that's fine. Or we can maintain occ array and for each block check free by scanning? But O(K) per block would be heavy. Better to keep occ array and prefix sum array that we recompute after each occupation. Since we only update one row per request (the chosen block), we can recompute prefix for that row quickly: For row x, after marking seats in range [yl, yr] as occupied, we recompute occ_prefix[x][0]=0, then for j=1..K: occ_prefix[x][j] = occ_prefix[x][j-1] + (1 if seat (x,j) occupied else 0). That's O(K) per request, which is fine.
Alternatively, we could maintain a bitset and use something like bit operations, but not needed.
Thus algorithm:
- Read N, K.
- Compute c = (K+1)//2.
- Precompute distance matrix d[x][y] = abs(x-c)+abs(y-c).
- For each row x (1-indexed), compute dist_prefix[x] array of length K+1: dist_prefix[x][0]=0; for j from 1..K: dist_prefix[x][j] = dist_prefix[x][j-1] + d[x][j].
- Initialize occ array: occ[x][j] = False (or 0) for all seats. occ_prefix[x] array of length K+1 with zeros.
- For each request M in list:
- best_total = large (maybe INF = 10**9)
- best_row = -1; best_yl = -1
- For x in 1..K:
- For yl in 1..K-M+1:
- yr = yl+M-1
- if occ_prefix[x][yr] - occ_prefix[x][yl-1] == 0:
- sum = dist_prefix[x][yr] - dist_prefix[x][yl-1]
- Compare: if sum < best_total or (sum == best_total and x < best_row) or (sum == best_total and x == best_row and yl < best_yl):
- update best_total, best_row, best_yl
- For yl in 1..K-M+1:
- If best_row == -1: print(-1)
- Else:
- yr = best_yl + M - 1
- Print(best_row, best_yl, yr)
- Mark seats: for y in range(best_yl, yr+1): occ[best_row][y] = 1
- Recompute occ_prefix for row best_row: occ_prefix[best_row][0]=0; for j in 1..K: occ_prefix[best_row][j] = occ_prefix[best_row][j-1] + occ[best_row][j]
This works.
Edge cases: M can be > available free seats? But we only consider if free. If no block found, output -1.
Note: The hall size K is odd. But even if not, problem statement says K is odd. So c = (K+1)/2 integer.
Complexities: O(N * K^2) ~ 1000 * 9801 = 9.8e6 iterations, each with O(1). Marking O(K) per request, so overall fine.
We should be careful with indexing: Use 1-indexing for rows and seats.
Let's implement.
But wait, there might be nuance: For each request, we need to find M successive seats in one row. Is it possible that there are multiple rows and we need to consider all possibilities? Yes.
One more nuance: The order of tie-breaking: "If the amount of minimum function values is more than one, the program should choose the one that is closer to the screen (i.e. the row number x is lower). If the variants are still multiple, it should choose the one with the minimum yl." So indeed, row first, then start column.
Thus the comparison order: (total, row, yl). But note: row smaller is better. So we compare by total ascending, then row ascending, then yl ascending.
Hence we can structure as tuple (total, row, yl) for each candidate and take min.
Implementation: Since K small, we could generate all candidate blocks, filter free, compute sum, then take min via tuple. But generating all blocks (rows*possible starts) is only 9801, so we can just loop.
Potential performance: For each block, we need to check if free using prefix sums: occ_prefix[x][yr] - occ_prefix[x][yl-1] == 0. This is O(1). But we also need to compute sum via dist_prefix similarly. All fine.
We need to precompute dist_prefix per row. Let's do that.
Now implement.
Pseudo:
def solve(): import sys input = sys.stdin.readline N, K = map(int, input().split()) M_list = list(map(int, input().split())) c = (K+1)//2 # Precompute distance and prefix sums per row (1-indexed) # We'll have lists of length K+1 dist_prefix = [[0]*(K+1) for _ in range(K+1)] # row index from 1..K, but index 0 remains 0 for x in range(1, K+1): row_prefix = dist_prefix[x] s = 0 for y in range(1, K+1): d = abs(x - c) + abs(y - c) s += d row_prefix[y] = s
# Occupancy prefix occ_prefix = [[0]*(K+1) for _ in range(K+1)] # will maintain # Actually we also need occ array to update, but we can update occ_prefix directly? # We'll maintain occ array separately to simplify updates. occupied = [[False]*(K+1) for _ in range(K+1)] # 1-indexed columns, row out_lines = [] for M in M_list: best_total = None best_row = -1 best_yl = -1 for x in range(1, K+1): # For this row, we can pre-get its occ_prefix row and dist_prefix row for speed occ_row = occ_prefix[x] dist_row = dist_prefix[x] # Iterate yl max_yl = K - M + 1 for yl in range(1, max_yl+1): yr = yl + M - 1 if occ_row[yr] - occ_row[yl-1] != 0: continue total = dist_row[yr] - dist_row[yl-1] if best_total is None or total < best_total or (total == best_total and x < best_row) or (total == best_total and x == best_row and yl < best_yl): best_total = total best_row = x best_yl = yl if best_row == -1: out_lines.append("-1") else: yr = best_yl + M - 1 out_lines.append(f"{best_row} {best_yl} {yr}") # Mark seats occupied row_occ = occupied[best_row] for y in range(best_yl, yr+1): row_occ[y] = True # Recompute occ_prefix for that row occ_prefix_row = occ_prefix[best_row] s = 0 for y in range(1, K+1): s += 1 if row_occ[y] else 0 occ_prefix_row[y] = s sys.stdout.write("\n".join(out_lines))Test with examples.
Example1: N=2,K=1,M=[1,1] c=1 dist_prefix[1][1]=0 Initial all free. M=1: loop rows=1, yl=1 only: free, total=0, best_total=0, best_row=1,best_yl=1 -> output 1 1 1. Mark seat (1,1) occupied. M=1: row1 yl=1: occ_prefix shows seat occupied, so no free. So no candidate, output -1. matches.
Example2 as above.
Check also potential tie-breaking: if same row and same total but multiple yl, we choose smallest yl. That is covered.
Edge cases: M = K. Then only yl=1 possible per row. So candidate per row if whole row free. We'll compare totals.
Now complexity: For each request, we loop rows up to K (max 99) and start positions up to K-M+1 (worst when M=1, start positions=99). So about 9801 iterations per request. 1000 * 9801 = 9.8e6, which is fine.
But is there any subtlety? The problem states: "All cinema halls in Berland are rectangles with K rows of K seats each, and K is an odd number." So K odd.
Also, "If the amount of minimum function values is more than one, the program should choose the one that is closer to the screen (i.e. the row number x is lower)." So row number lower is closer? In cinemas, typically lower row numbers are closer to the screen? Usually row numbers increase away from screen? In the example, after first request occupied center (2,2), for M=2 they chose row1 (closer) rather than row3. So yes lower row number is closer.
Thus our logic matches.
Now potential pitfalls: When best_total is None? If we find no candidate, we output -1. That's correct.
Now, do we need to consider that after marking seats, the prefix sums are updated correctly? Yes.
Now, we need to store occupied as boolean or int; marking as True, and compute prefix sums each time for the affected row: we can just compute prefix from scratch because K is small.
Alternatively, we could maintain occ_prefix without recomputing fully: we can update by adding 1 to occ_prefix for columns >= yl within the row, but recompute is easier and safe.
Now final answer: implement solve().
But wait: We might be able to further optimize by precomputing all possible blocks and using some data structure to quickly find free blocks? Not necessary.
One more check: The total distance sum we compute as described: sum of d[x][y] for all seats in block. That's what we used. In example M=2, we got totals 3 for all blocks. Confirm with d values: row1 (1,1)=2, (1,2)=1 sum=3; (1,2)-(1,3)=1+2=3; row3 (3,1)=2,(3,2)=1 sum=3; row3 (3,2)-(3,3)=1+2=3. Yes.
Thus solution correct.
Now, about input format: N and K on first line, second line N integers Mi. There's possibly multiple lines? but spec says second line contains N space-separated integers. So we can read all at once.
Now, output N lines.
Now code.
Potential memory: dist_prefix is (K+1)*(K+1) ≤ 10000, fine.
We'll implement with 0-indexing internally? Might be easier to keep 1-indexed.
I'll write code.
Edge Cases:
- K=99, N=1000, M might be large, but algorithm fine.
Now let's consider if there is any nuance about "total seats remoteness from the center" maybe it is sum of distances squared? But from example it's Manhattan sum. So we are correct.
Thus final answer.
But wait: In the problem statement, they say "the function value of total seats remoteness from the center. Say, — the row and the seat numbers of the most 'central' seat. Then the function value of seats remoteness from the hall center is ." It could be interpreted as something like sum of squared distances? But the example fits Manhattan sum. So safe.
Now, check if there is any possibility that the tie-breaking also includes something else? Already covered.
Thus final solution.
Now test with a small custom case: K=3, initial all free, request M=3: Which row is chosen? All rows have full free. Compute totals: Row1: seats (1,1)=2, (1,2)=1, (1,3)=2 sum=5. Row2: seats (2,1)=1, (2,2)=0, (2,3)=1 sum=2. Row3: seats (3,1)=2, (3,2)=1, (3,3)=2 sum=5. So row2 chosen (since sum=2 minimal). Output "2 1 3". Good.
Now after occupying row2 full, next M=1: free seats: others. distances: row1 seat1=2, seat2=1, seat3=2; row3 seat1=2, seat2=1, seat3=2. Minimal distance=1, and there are two seats: (1,2) and (3,2). Tie on total (1), then row1 lower => (1,2). So output "1 2 2". Good.
Alright.
Now, there's a nuance: the total remoteness function may be defined as "the sum of the squares of the distances"? Let's double-check with example: For M=2, if it were squares, row1 block (1,1)-(1,2): distances squared: 2^2 + 1^2 = 5; (1,2)-(1,3): 1^2+2^2=5; row3 blocks similar 5. So sum=5, still tie. But what about row1 block (1,1)-(1,2) vs row3 block (3,1)-(3,2) both 5, tie on sum, then row1 lower => same. So example still matches. For M=1 first request: distances squared: (2,2)=0, (2,1)=1, (2,3)=1, (1,2)=1, etc. So still choose (2,2). So squares also works? But also for M=3 first request (if all free) squares: row1 sum=2^2+1^2+2^2=9, row2 sum=1+0+1=2, row3 sum=9. So row2 chosen. Still works. So both Manhattan and squared yield same? Not always. For example, consider K=5, center=3, distances: (3,1)=2, (3,5)=2, (4,4)=? Actually need a case where sums differ. But the problem likely uses Manhattan because it's typical and formula image probably shows absolute values. Also the phrase "|x - c| + |y - c|" is common. So we stick with Manhattan.
Thus, solution is as above.
Now code in Python:
Implementation details:
- Use sys.stdin.read or sys.stdin.readline for speed. Since N up to 1000, fine.
- Use loops.
Potential micro-optimizations: Precompute d and dist_prefix as lists of lists. Use local variables inside loops to avoid attribute lookups.
We'll write:
def solve(): import sys data = sys.stdin.read().strip().split() if not data: return it = iter(data) N = int(next(it)) K = int(next(it)) M_list = [int(next(it)) for _ in range(N)] c = (K+1)//2 # precompute distances and prefix dist_prefix = [[0](K+1) for _ in range(K+1)] for x in range(1, K+1): dx = abs(x - c) pref = dist_prefix[x] s = 0 for y in range(1, K+1): d = dx + abs(y - c) s += d pref[y] = s # occupancy arrays occupied = [[False](K+1) for _ in range(K+1)] occ_prefix = [[0]*(K+1) for _ in range(K+1)] out = [] for M in M_list: best_total = None best_row = -1 best_yl = -1 # iterate rows for x in range(1, K+1): occ_row = occ_prefix[x] dist_row = dist_prefix[x] # iterate yl max_yl = K - M + 1 for yl in range(1, max_yl+1): yr = yl + M - 1 if occ_row[yr] - occ_row[yl-1] != 0: continue total = dist_row[yr] - dist_row[yl-1] if best_total is None or total < best_total or (total == best_total and x < best_row) or (total == best_total and x == best_row and yl < best_yl): best_total = total best_row = x best_yl = yl if best_row == -1: out.append("-1") else: yr = best_yl + M - 1 out.append(f"{best_row} {best_yl} {yr}") # mark occupied row_occ = occupied[best_row] for y in range(best_yl, yr+1): row_occ[y] = True # recompute prefix for that row pref = occ_prefix[best_row] s = 0 for y in range(1, K+1): if row_occ[y]: s += 1 pref[y] = s sys.stdout.write("\n".join(out))
That should work.
Double-check recompute prefix: We set s=0, then for y=1..K: s += 1 if occupied else 0; pref[y] = s. Good.
Test with example:
Input: 2 1 1 1
Output: 1 1 1 -1
Matches.
Second example:
Input: 4 3 1 2 3 1
Our code should produce: 2 2 2 1 1 2 3 1 3 2 1 1
We can test manually but trust.
Now consider a case where there are multiple rows with same total and row number? Actually row number distinct per row, so if same total but different rows, we pick smallest row. That's correct. If same row but multiple blocks with same total (like M=2, row1 had two blocks with same total), we pick smallest yl. So code uses if (total == best_total and x < best_row) ... else if total == best_total and x == best_row and yl < best_yl. That's correct because we update only when strictly better according to criteria. But we need to be careful: If best_total is None initially, we set. Then for later candidates, if total == best_total, we need to check row and yl. But we also have condition (total == best_total and x < best_row) OR (total == best_total and x == best_row and yl < best_yl). This will update if either row is smaller, or row equal and yl smaller. However what if total == best_total and row < best_row but we don't want to also require that? The condition (total == best_total and x < best_row) is enough. But we also need to handle the case where total < best_total. So the combined condition is: if best_total is None or total < best_total or (total == best_total and (x < best_row or (x == best_row and yl < best_yl))). In our code we wrote: if best_total is None or total < best_total or (total == best_total and x < best_row) or (total == best_total and x == best_row and yl < best_yl). That works because if x < best_row, then the second part triggers even if the third part doesn't. But note if x < best_row, then the third part (x == best_row and yl < best_yl) is false, but the second part is true. So update. Similarly, if x == best_row and yl < best_yl, then second part false but third part true. So that's fine.
But one subtlety: When total == best_total and x < best_row, we update. However what if best_total is None? We already have that case. So fine.
Now about integer overflow: total sum of distances per block: max per seat distance = (K-1)+(K-1) = 2K-2 ≈ 196 for K=99, times M max 99 = ~19404, well within int.
Now, we should ensure that when M=0? Not possible, M ≥ 1.
Now we need to output each line. Good.
Now we should test additional custom cases to verify tie-breaking.
Case: K=3, all free, M=1. Should pick (2,2). Our code: For each row x=1..3, yl=1..3 (since M=1). Compute total = d[x][yl]. The minimum is 0 at (2,2). So best_total becomes 0 at row2 yl=2. Later candidates with total=0? none. So pick (2,2). Good.
Case: K=3, all free, M=2. All four blocks have total=3. Tie. We need to pick row with smallest x: row1. Among row1, yl smallest is 1. So output (1,1,2). Our code: As we iterate rows from 1 to 3, we will encounter row1 first. For row1, yl=1 gives total=3, best_total None => set best_total=3, best_row=1, best_yl=1. Then row1 yl=2: total=3, total==best_total and x==best_row (1) and yl=2 > best_yl=1, so not update. Then row2: all blocks will be invalid because they contain occupied? Actually all free, but row2 blocks: yl=1 (seats 1,2) total = d[2][1]+d[2][2] =1+0=1? Wait d[2][1]=|2-2|+|1-2|=0+1=1; d[2][2]=0 => total=1. Actually for row2 M=2, we have blocks (2,1)-(2,2) total =1+0=1, and (2,2)-(2,3) total=0+1=1. So those totals are 1, not 3! But in example with some seats occupied, row2 had occupied (2,2) so those blocks were not free. But if all free, row2 blocks would be considered and they have total 1, which is less than row1's total 3. So the best would be row2, not row1. Indeed, if all free, for M=2, row2 blocks have lower total. Let's verify: row2 (2,1)-(2,2): distances 1 and 0 sum=1; row2 (2,2)-(2,3): 0+1=1; row1 blocks sum=3; row3 blocks sum=3. So the algorithm would choose row2 block, and then between two blocks in row2, they tie on total, same row, so choose smaller yl: yl=1. So output (2,1,2). That would be correct according to the algorithm. So our code would pick row2 because it's smaller total. That's correct. So example earlier had row2 seat2 occupied, causing row2 blocks unavailable. So our code works.
Now, is there any requirement to output -1 when no placement? Yes.
Now, potential bug: When we mark occupied, we use occupied array, but we don't update occ_prefix for other rows. That's fine because we recompute only for affected row.
Now, ensure that we recompute occ_prefix correctly after each marking: we recompute from scratch for that row. Could also update incrementally but fine.
Now, we must be careful: occ_prefix is used to check free segments; we update after marking. So it's consistent.
Now, let's think about memory: occupied and occ_prefix are 100x100 each, fine.
Now, final code.
But wait: In the input, K can be up to 99, which is odd. That's guaranteed.
One more nuance: The problem says "All cinema halls in Berland are rectangles with K rows of K seats each, and K is an odd number." So K is odd. So c integer.
Now, test with a larger example manually:
K=5, center=3. Precompute distances. Let's simulate a few requests manually to ensure code behaves.
But trust.
Now, consider possibility: When we compute total remoteness, is it sum of distances from center per seat? Yes.
Now, we should confirm that the algorithm indeed chooses the block that minimizes that sum. That is what we implemented.
Now, final answer: Provide code.
Now, we can do some optimization: Instead of recomputing occ_prefix for the row each time, we could update it by adding 1 for the range, but it's fine.
Now, one edge: In the loop for each request, we iterate rows from 1..K and start columns from 1..K-M+1. When M is 0? not possible.
Now, also note: In some cases, if K is small like 1, M can be 1. That works.
Now, confirm that we treat indices correctly: occ_prefix[x][yr] - occ_prefix[x][yl-1] gives count of occupied seats in [yl, yr]. We need to check if it's zero.
Now, we need to store occ_prefix as list of lists of integers. For each row, occ_prefix[0] is 0 (we don't use index 0). We'll compute it after marking. For rows that never get occupied, occ_prefix remains all zeros. Good.
Now, we should set occ_prefix[best_row] after marking: we compute from y=1 to K, but we must also set occ_prefix[best_row][0] = 0. Actually we don't use index 0, but we can keep as is (since we never access occ_prefix[x][0] except yl-1 might be 0; when yl=1, we need occ_prefix[x][0] which we defined as 0. In our occ_prefix list, we have length K+1; index 0 is present and we haven't set it explicitly after recomputation, but we can set it to 0 before recompute. However we currently set s=0 and then for y from 1..K we assign pref[y] = s. We didn't assign pref[0] after marking; but originally all rows had occ_prefix[x][0] = 0 because we initialized occ_prefix with all zeros. However, after marking, we only assign pref[y] for y=1..K; pref[0] remains as previous value (which was 0). So it's still 0. So okay.
Now, ensure that when we check occ_row[yl-1], if yl=1, then yl-1=0, and occ_row[0] is 0 because occ_prefix[x][0] is 0. Good.
Now, the code seems correct.
Now, we can produce final answer.
But before finalizing, consider if there is any other interpretation of the "remoteness" function: Could it be sum of squares of distances? Or sum of distances? As argued, both work for examples, but the problem statement likely meant Manhattan distance because they used absolute values in the image. So we go with Manhattan.
Now, we can also check if there is any nuance regarding the "center" seat: They said "the row and the seat numbers of the most 'central' seat." For odd K, that is (c,c). So we used that.
Now, final code.
We should include a if name == "main": solve() pattern.
Now, let's test with sample input manually.
We'll write code and run mentally.
First sample:
Input: 2 1 1 1
K=1, c=1. dist_prefix[1][1]=0.
occupied all false. occ_prefix all zeros.
Request M=1: best_total=None. x=1: occ_row = occ_prefix[1] = [0,0? Actually list length 2: index 0:0, index1:0. max_yl = 1-1+1=1? Actually K - M + 1 = 1-1+1=1. yl=1, yr=1: occ_row[1]-occ_row[0]=0 => free. total = dist_prefix[1][1]-dist_prefix[1][0]=0-0=0. update best_total=0, best_row=1, best_yl=1. Output: "1 1 1". Mark occupied[1][1]=True. Recompute occ_prefix for row1: s=0; for y=1: s=1, pref[1]=1.
Next request M=1: x=1: occ_row[1]-occ_row[0]=1-0=1 !=0 => not free. No candidates, best_row stays -1 => output -1.
Matches.
Second sample:
Input: 4 3 1 2 3 1
We'll simulate step by step.
K=3, c=2. Precompute distances (as earlier). dist_prefix rows: Row1: distances: (1,1)=2, (1,2)=1, (1,3)=2 => prefix: [0,2,3,5]? Actually prefix[1]=2, prefix[2]=3, prefix[3]=5. Row2: (2,1)=1, (2,2)=0, (2,3)=1 => prefix: 1,1,2? Wait compute: prefix[1]=1, prefix[2]=1 (since 1+0=1), prefix[3]=2 (1+0+1=2). Actually careful: prefix[2] = d21 + d22 = 1+0=1, prefix[3] = d21+d22+d23 = 1+0+1=2. Row3: (3,1)=2, (3,2)=1, (3,3)=2 => prefix: 2,3,5.
occupied all false initially, occ_prefix all zeros.
Request M=1: Loop rows. Row1: yl=1: total=2; update best_total=2,best_row=1,best_yl=1. yl=2: total=1; since total=1 < 2, update: best_total=1,best_row=1,best_yl=2? Actually total=1 is less than 2, so update: best_total=1,best_row=1,best_yl=2. yl=3: total=2; skip. Row2: yl=1: total=1; total=1 == best_total? best_total=1; compare x: x=2 > best_row=1, so not update. yl=2: total=0; total=0 < 1 => update best_total=0,best_row=2,best_yl=2. yl=3: total=1; total=1 > best_total=0, skip. Row3: yl=1: total=2 >0 skip yl=2: total=1 >0 skip yl=3: total=2 skip. So best: row2 yl=2 -> output "2 2 2". Mark occupied[2][2]=True. Recompute occ_prefix for row2: occ[2][1]=False, [2]=True, [3]=False -> prefix: [0,0,1,1]? Actually recompute: s=0; y=1: s=0, pref[1]=0; y=2: s=1, pref[2]=1; y=3: s=1, pref[3]=1.
Request M=2: Loop rows: Row1: occ_row1 all zeros? No row1 still all free; occ_prefix[1] all zeros. Dist row1 prefix as above. yl=1, yr=2: occ check: occ[1][2]-occ[1][0]=0 => free. total = dist_prefix[1][2]-dist_prefix[1][0]=3-0=3. (Note: prefix[0]=0, we didn't set, but it's 0). So total=3. best_total=None -> set best_total=3,best_row=1,best_yl=1. yl=2, yr=3: occ check: free? yes. total = dist_prefix[1][3]-dist_prefix[1][1]=5-2=3? Actually careful: dist_prefix[1][3] - dist_prefix[1][1] = 5 - 2 = 3. Compare: total=3 == best_total, row=1==best_row, yl=2 > best_yl=1 => no update. Row2: occ_row2 prefix: [0,0,1,1] (index 0:0,1:0,2:1,3:1) yl=1, yr=2: occ check: occ[2][2] - occ[2][0] = 1 - 0 =1 => not free. yl=2, yr=3: occ[2][3] - occ[2][1] = 1 - 0 =1 => not free. So skip. Row3: occ_row3 all zero. Dist row3: prefix[1]=2, [2]=3, [3]=5. yl=1, yr=2: occ free; total = dist[3][2]-dist[3][0]=3-0=3. Compare: total=3 == best_total, row=3 > best_row=1 => no update. yl=2, yr=3: total = dist[3][3]-dist[3][1]=5-2=3. Compare: total=3 == best_total, row=3>1 => no update. Thus best is row1 yl=1 -> output "1 1 2". Mark occupied row1 seats 1 and 2 true. Recompute occ_prefix row1: occ[1][1]=True, [2]=True, [3]=False -> prefix: [0,1,2,2].
Request M=3: Loop rows: Row1: occ_row1 prefix: [0,1,2,2] yl=1, yr=3: occ[1][3]-occ[1][0]=2-0=2 !=0 -> not free. Row2: occ_row2 prefix: [0,0,1,1] (since row2 only seat2 occupied) yl=1, yr=3: occ[2][3]-occ[2][0]=1-0=1 !=0 -> not free. Row3: occ_row3 prefix: all zero. yl=1, yr=3: free. total = dist[3][3]-dist[3][0]=5-0=5. best_total set to 5, best_row=3,best_yl=1. Only block. So output "3 1 3". Mark occupied row3 seats 1,2,3 true. Recompute occ_prefix row3: [0,1,2,3]? Actually occ row3 now all True: prefix: 1,2,3.
Request M=1: Loop rows: Row1: occ_row1 prefix [0,1,2,2] (seats1,2 occupied, seat3 free) yl=1: occ[1][1]-occ[1][0]=1 -> not free. yl=2: occ[1][2]-occ[1][1]=2-1=1 -> not free. yl=3: occ[1][3]-occ[1][2]=2-2=0 -> free. total = dist[1][3]-dist[1][2]=5-3=2? Actually dist[1] prefix: [0,2,3,5]? Wait we earlier computed dist_prefix[1] as: index1:2, index2:3, index3:5. So total = 5 - 3 = 2. So candidate total=2. Row2: occ_row2 prefix [0,0,1,1] (seat2 occupied) yl=1: free? occ[2][1]-occ[2][0]=0 => free. total = dist[2][1]-dist[2][0]=1-0=1. yl=2: not free (occupied count 1) yl=3: occ[2][3]-occ[2][2]=1-1=0? Actually occ[2][3]=1, occ[2][2]=1, so diff=0? Wait occ[2][3] = cumulative occupied up to seat3: seat1 free, seat2 occ, seat3 free? Actually after marking row3, row2 still has only seat2 occupied. So occ[2] prefix: after recompute: seat1:0, seat2:1, seat3:1? Because seat3 free, cumulative after seat3 is still 1. So occ[2][3]=1, occ[2][2]=1, diff=0 => free. So yl=3: free. total = dist[2][3]-dist[2][2]=2-1=1. So two candidates: (2,1) and (2,3) both total=1. Row3: all occupied, no free. Now we evaluate best_total: First candidate row1 yl=3 total=2, best_total=2, best_row=1,best_yl=3. Then row2 yl=1 total=1, total < best_total (2) => update: best_total=1, best_row=2, best_yl=1. Then row2 yl=3 total=1, total==best_total=1, row=2==best_row=2, yl=3 > best_yl=1 => no update. Thus best is row2 yl=1 => output "2 1 1". matches.
Works.
Thus implementation is correct.
Now think about potential pitfalls: M may be zero? No.
Now, consider if there are multiple rows with same total, row lower wins, but we iterate rows from 1 to K, so we will encounter lower rows first. However our update condition when total==best_total and x < best_row will only update if we find a row with smaller row number later? Actually if we iterate rows from 1 to K, we will see row1 first, then row2, etc. If we set best from row1 initially, later rows with same total but higher row number will not satisfy x < best_row, so they won't be chosen. That's correct because we want lowest row number. However, what if we encounter a row with same total but a smaller yl after a larger yl? Since we iterate yl from 1 to K-M+1 in order, we will first see smaller yl, so best_yl will be smallest automatically when row same. But if we find a later row with same total but row number smaller? Since we iterate rows in increasing order, we will first encounter smaller row numbers, so they will be set as best, and later rows with larger row numbers won't beat it because x < best_row is false (since best_row is smaller). So the order of iteration ensures that we choose the correct one with tie-breaking. However, there is nuance: if we start with best_total None, we set first candidate. Then later if we find a candidate with same total but row number smaller? That can only happen if we later see a smaller row number than the one we already have; but because we iterate rows in increasing order, if we already processed row1, best_row could be 1, then later rows are higher, so row < best_row never true. So no issue. But what if we process rows in descending order? It could matter. But we are iterating ascending, which is natural. So it's okay. However, if we had iterated rows arbitrarily, we would need to use condition correctly. Since we do 1..K, it's fine.
But careful: When we start with best_total None, we set the first free candidate we encounter. That candidate might not be the absolute best if there is another with equal total but lower row number? Since we go ascending rows, the first candidate will be from the smallest row that has any free block. However, it's possible that this candidate has total larger than other blocks in later rows? Actually we compare total first. So if a later row has lower total, it will update regardless of row. So the order doesn't matter because we compare based on total, then row, then yl. Since we check all candidates, the final best is the one that is minimal according to the lexicographic order (total, row, yl). Our update condition ensures that we get the globally minimal tuple, regardless of iteration order (as long as we compare all). But because we update only when better, the final best will be the minimum. So iteration order does not need to be specific. Our condition covers all cases.
But we need to be careful: When best_total is not None, and we have a candidate with total == best_total and x < best_row, we update. That's correct. Also if x == best_row and yl < best_yl, we update. So final best will be minimal according to tuple (total, row, yl). However, our condition also includes if total < best_total, update. That's standard. So final best is correct.
Now one more nuance: For ties on total, row lower is better. But if we find a candidate with same total and same row but smaller yl, we update. So it's fine.
Now we must ensure that we treat the case where best_total is set but we later find a candidate with same total but row number larger but with smaller yl? Not relevant because if row larger, row is worse, so we should not update. Our condition does not update if row larger. So fine.
Now, code should be robust.
Now, memory: We have dist_prefix as a list of lists of length K+1, but we only use indices 1..K. That's okay.
Potential small optimization: For each row, we could precompute an array of distances and then compute sums on the fly without prefix. But prefix is fine.
Now, we should also consider if K can be as large as 99, but the input might have N up to 1000, reading via sys.stdin.read is fine.
Now, consider if we need to handle multiple test cases? The problem is a single case.
Now, final solution.
But wait: The problem statement says: "The first line contains two integers N and K (1 ≤ N ≤ 1000, 1 ≤ K ≤ 99) — the amount of requests and the hall size respectively." So it's just one test case.
Now, we should output each answer on a new line.
Now, let's write the final solution.
We'll include a main guard.
Now, I'll produce final answer. ```python import sys
def solve() -> None: data = sys.stdin.read().strip().split() if not data: return it = iter(data) N = int(next(it)) K = int(next(it)) requests = [int(next(it)) for _ in range(N)]
# centre seat (both row and column) c = (K + 1) // 2 # prefix sums of distances d = |x-c| + |y-c| # rows and columns are 1‑based, index 0 is kept as 0 dist_prefix = [[0] * (K + 1) for _ in range(K + 1)] for x in range(1, K + 1): dx = abs(x - c) pref = dist_prefix[x] s = 0 for y in range(1, K + 1): s += dx + abs(y - c) pref[y] = s # occupancy and its prefix sums occupied = [[False] * (K + 1) for _ in range(K + 1)] occ_prefix = [[0] * (K + 1) for _ in range(K + 1)] out_lines = [] for M in requests: best_total = None best_row = -1 best_yl = -1 for x in range(1, K + 1): occ_row = occ_prefix[x] dist_row = dist_prefix[x] max_yl = K - M + 1 for yl in range(1, max_yl + 1): yr = yl + M