Virtual Memory Page Replacement Simulation

Virtual memory is an important storage management technology in modern operating systems. In this problem, you are required to simulate a page replacement algorithm for managing virtual memory accesses.

Each process has its own virtual memory pages and performs read/write operations on a per-page basis. Ideally, all pages should reside in the main memory for fast access, but due to limited memory capacity, only a subset of pages are kept in memory. To resolve this, an operating system uses a virtual memory technique that uses secondary storage to emulate an expanded memory.

The system comprises n physical memory pages (initially all empty) and receives m commands. Each command is a request to access a virtual page with page number \(P\). The simulation of each access follows these steps:

• Step 1: Check if the page exists in physical memory. If it does, simply increase its access count and finish the operation.
• Step 2: If the page is not in memory and there is an empty page available, load the requested page into this empty slot. Initialize its access count to 1 and record the load time \(t\).
• Step 3: If there is no free slot, choose a page to replace. The victim is selected as the page with the smallest access count since it was loaded into memory. In case of a tie (i.e. multiple pages having the same minimum access count), the page that was loaded earliest (i.e. with the smallest \(t\)) is replaced. The new page is then loaded into that slot with an access count of 1 and the current time \(t\).
• Step 4: End the operation.

Note that the access count is only maintained for the current instance of the page in memory. If a page is replaced and later reloaded, its previous access count is discarded.

After executing all \(m\) commands, output the final state of physical memory as a sequence of \(n\) integers. Each slot (from index 0 to \(n-1\)) should display the page number currently loaded; if a slot is still empty, output -1 for that slot.

inputFormat

The first line contains two integers \(n\) and \(m\) (\(1 \leq n, m \leq 10^5\)), representing the number of physical memory pages and the number of access commands respectively.

The following \(m\) lines each contain an integer \(P\), the virtual memory page number to be accessed.

outputFormat

Output a single line containing \(n\) space-separated integers. For each memory slot (indexed from 0 to \(n-1\)), output the page number loaded in that slot. If a slot is empty, output -1.

sample

3 6
1
2
3
2
4
1

4 2 1