Memory Allocation Simulation

This problem simulates a memory allocation system. Memory is divided into individual cells identified by consecutive addresses starting from \(0\). An address block is defined as a contiguous group of memory cells. At any time \(T\), a process arriving with a memory requirement \(M\) and running time \(P\) is allocated a free contiguous memory block of size \(M\) if such a block exists. If there are multiple candidates, the block with the smallest starting address is chosen. If no such block exists, the process is put into a waiting queue.

The waiting queue is served in a first-come-first-served manner. At any moment that memory is freed (when a process completes its execution), the process at the front of the waiting queue is checked, and if a suitable free block of size \(M\) is found, it is allocated immediately. Memory allocated to a process is occupied for its entire running time \(P\) starting from when it is allocated, and then the occupied block is freed, potentially merging with adjacent free blocks.

You are given the total memory size and a list of processes. Each process is described by its arrival time \(T\), memory requirement \(M\), and processing time \(P\). Your task is to simulate the allocation process and output, for each process (in the order of input), the starting address of the allocated memory block.

Note: The simulation always allocates a block when it becomes available. Merging of adjacent free blocks should be properly handled upon releasing memory.

inputFormat

The first line contains two integers \(S\) and \(n\) representing the total memory size and the number of processes, respectively.

Each of the next \(n\) lines contains three integers: \(T\), \(M\), and \(P\), where:

• \(T\) is the arrival time of the process.
• \(M\) is the number of memory cells required by the process.
• \(P\) is the processing (running) time of the process.

Processes are provided in the input order. Note that processes may not be sorted by their arrival time \(T\); you must handle events in chronological order.

outputFormat

Output \(n\) lines. For each process (in the same order as the input), output a single integer representing the starting address of the allocated contiguous memory block.

sample

10 3
0 3 5
1 4 3
2 3 4

0
3
7