运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。 获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回-1。 写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。 要求get和put都为O(1)的时间复杂度。

输入描述:

第一行是两个整数N,M。代表共有N次操作，缓存容量为M，用空格分隔。第2~n+1行是n次操作，格式为"PUT x y"或"GET x"。x和y为题面所要求的数字。

输出描述:

对于每个GET操作，输出一行数字作为结果。

备注:

x和y都是正整数，1=n=1e5，1=m=1e5