import java.util.Scanner;

public class LRU {

    public static void main(String[] args) {
    // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);

        
        System.out.print("Enter no of Frames: ");
        int n = sc.nextInt();

        System.out.print("Enter number of Pages: ");
        int m = sc.nextInt();

        int[] ref = new int[m];
        System.out.print("Enter String: ");
        for (int i = 0; i < m; i++) {
            ref[i] = sc.nextInt();
        }

        int[] buffer = new int[n];
        for (int i = 0; i < n; i++) {
            buffer[i] = -1;
        }

        int[][] memlayout = new int[n][m];
        char[] mark = new char[m];
        int hit = 0, fault = 0;

        
        int[] lastUsed = new int[n];

        for (int i = 0; i < m; i++) {
            int search = -1;

            for (int j = 0; j < n; j++) {
                if (buffer[j] == ref[i]) {
                    hit++;
                    search = j;
                    mark[i] = '#';
                    lastUsed[j] = i; 
                    break;
                }
            }

          
            if (search == -1) {
                int emptyIndex = -1;

                for (int j = 0; j < n; j++) {
                    if (buffer[j] == -1) {
                        emptyIndex = j;
                        break;
                    }
                }

                if (emptyIndex != -1) { 
                   
                    buffer[emptyIndex] = ref[i];
                    lastUsed[emptyIndex] = i;
                } else {
                    
                    int lruIndex = 0;
                    for (int j = 1; j < n; j++) {
                        if (lastUsed[j] < lastUsed[lruIndex]) {
                            lruIndex = j;
                        }
                    }
                    buffer[lruIndex] = ref[i];
                    lastUsed[lruIndex] = i;
                }
                fault++;
                mark[i] = '*';
            }

          
            for (int j = 0; j < n; j++) {
                memlayout[j][i] = buffer[j];
            }
        }

   
        System.out.print("\\nREFERENCE STRING:\\n");
        for (int i = 0; i < m; i++) {
            System.out.print(ref[i] + "\\t");
        }
        System.out.println();

        System.out.println("Memory Layout:");
        for (int frame = 0; frame < n; frame++) {
            for (int string = 0; string < m; string++) {
                if (memlayout[frame][string] == -1) {
                    System.out.print(" \\t");
                } else {
                    System.out.print(memlayout[frame][string] + "\\t");
                }
            }
            System.out.println();
        }

        System.out.print("Marks:\\n");
        for (int i = 0; i < m; i++) {
            System.out.print(mark[i] + "\\t");
        }
        System.out.println();

        System.out.println("Total Page Faults = " + fault);
        System.out.println("Total Hits = " + hit);

        sc.close();
    }
}