import java.util.HashMap;

public class SnapshotableMap {

    int id = 0;
    private HashMap<String, Integer> map = new HashMap();


    public void put(int key, int val){
        String strKey = buildKey(key, id);
        map.put(strKey, val);
    }

    public int get(int key){
        String mostRecentKey = buildKey(key, 0);
        for(int i = 1; i<=id; i++){
            String currentKey = buildKey(key, i);
            if(map.containsKey(currentKey)){
                mostRecentKey = currentKey;
            }else{
                break;
            }
        }

        return map.get(mostRecentKey);
    }

    private String buildKey(int key, int snapshotId){
        return snapshotId + " " + key;
    }

    public int snapshot(){
        id++;
        return id-1;
    }

    public int get(int key, int snapshotId){
        return map.get(buildKey(key, snapshotId));
    }

}