import java.util.Scanner;

public class Optimal {

    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;

        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] = '#';
                    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];
                } else {

                    int replaceIndex = -1, farthest = i + 1;

                    for (int j = 0; j < n; j++) {
                        int nextUse = -1;
                        for (int k = i + 1; k < m; k++) {
                            if (buffer[j] == ref[k]) {
                                nextUse = k;
                                break;
                            }
                        }

                        if (nextUse == -1) { 
                           
                            replaceIndex = j;
                            break;
                        } else if (nextUse > farthest) {
                            farthest = nextUse;
                            replaceIndex = j;
                        }
                    }

                    buffer[replaceIndex] = ref[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();
    }
}