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

#include "lru.h"



struct lru *lru_create(int capacity) {
    struct lru *c = calloc(1, sizeof(struct lru));
    c->capacity = capacity;
    return c;
}

unsigned bucket_of(int key) {
    unsigned h = (unsigned)key * 2654435761u;
    return h % NBUCKETS;
}

void list_unlink(struct lru *c, struct entry *e) {
    if (e->prev) e->prev->next = e->next; else c->head = e->next;
    if (e->next) e->next->prev = e->prev; else c->tail = e->prev;
    e->prev = e->next = NULL;
}

void list_push_front(struct lru *c, struct entry *e) {
    e->prev = NULL;
    e->next = c->head;
    if (c->head) c->head->prev = e; else c->tail = e;
    c->head = e;
}

void bucket_remove(struct lru *c, struct entry *e) {
    unsigned b = bucket_of(e->key);
    struct entry **pp = &c->buckets[b];
    while (*pp && *pp != e) pp = &(*pp)->hnext;
    if (*pp) *pp = e->hnext;
}

int lru_get(struct lru *c, int key) {
    // TODO: find key in its bucket; on a hit, move the node to the front of
    //       the recency list and return its value; on a miss return -1.
    (void)c; (void)key;
    return -1;
}

void lru_put(struct lru *c, int key, int val) {
    // TODO: if key exists, update val and move it to the front. Otherwise, if
    //       size == capacity, evict the tail (print "evict <key>") first, then
    //       insert a new node at the front and in its bucket.
    (void)c; (void)key; (void)val;
}


int main(void) {
    int cap;
    if (scanf("%d", &cap) != 1) return 0;
    struct lru *c = lru_create(cap);
    char cmd[16];
    while (scanf("%15s", cmd) == 1) {
        if (strcmp(cmd, "put") == 0) {
            int k, v;
            if (scanf("%d %d", &k, &v) != 2) break;
            lru_put(c, k, v);
        } else if (strcmp(cmd, "get") == 0) {
            int k;
            if (scanf("%d", &k) != 1) break;
            int r = lru_get(c, k);
            if (r == -1) printf("get %d -> miss\n", k);
            else printf("get %d -> %d\n", k, r);
        }
    }
    return 0;
}