#include <stdio.h>
#include <stdlib.h>

// Page Replacement: FIFO & Optimal (Minimal Code for Paper)
int main() {
    int nf, np, i, j, k, pf, hit, idx, max_f, vic; // nf=frames, np=pages, pf=faults, idx=fifo_idx, max_f=max_future, vic=victim
    int *rs, *f; // rs=ref_string, f=frames

    printf("F N:"); scanf("%d%d", &nf, &np); // Frames, NumPages
    rs = malloc(np * sizeof(int));
    f = malloc(nf * sizeof(int));
    if(!rs || !f) return 1; // Basic alloc check
    printf("RS:"); for(i=0; i<np; i++) scanf("%d", &rs[i]); // Ref String

    // FIFO
    puts("FIFO"); pf=0; idx=0;
    for(k=0; k<nf; k++) f[k]=-1; // Init frames
    for(i=0; i<np; i++){ // Iterate ref string
        hit=0; for(k=0; k<nf; k++) if(f[k]==rs[i]) {hit=1; break;} // Check hit
        if(!hit){ // Page Fault
            pf++; f[idx]=rs[i]; idx=(idx+1)%nf; // Replace using FIFO index
        }
    }
    printf("F:%d\n", pf); // Print Faults

    // Optimal
    puts("OPT"); pf=0;
    for(k=0; k<nf; k++) f[k]=-1; // Re-init frames
    for(i=0; i<np; i++){ // Iterate ref string
        hit=0; for(k=0; k<nf; k++) if(f[k]==rs[i]) {hit=1; break;} // Check hit
        if(!hit){ // Page Fault
            pf++; int empty=-1; for(k=0; k<nf; k++) if(f[k]==-1) {empty=k; break;} // Find empty frame
            if(empty!=-1) f[empty]=rs[i]; // Use empty frame if available
            else { // No empty frames, find victim
                vic=0; max_f=-1; // Victim index, max future distance
                for(k=0; k<nf; k++){ // Check each current frame 'f[k]'
                    int fut=-1; // Index of next use for f[k]
                    for(j=i+1; j<np; j++) if(f[k]==rs[j]) {fut=j; break;} // Look ahead
                    if(fut==-1) {vic=k; break;} // f[k] not used again? Best victim. Stop search.
                    if(fut>max_f) {max_f=fut; vic=k;} // f[k] used later than current max? Update victim.
                }
                f[vic]=rs[i]; // Replace victim frame
            }
        }
    }
    printf("F:%d\n", pf); // Print Faults

    free(rs); free(f); // Free memory
    return 0;
}