在线编程：O(1) LRU缓存

实现哈希与双向链表一致的get/put。

输入：第一行 capacity、q，随后 q 条 GET key 或 PUT key value。
输出：每条GET输出值，不存在输出-1；PUT无输出。
约束：0≤capacity≤100000，1≤q≤200000，key/value不含空白。

使用 Python 3 从标准输入读取，向标准输出写出唯一规定结果；不得读取文件或网络。

使用 Python 3 标准输入输出；不得使用第三方包。必须覆盖题面边界，不能只针对样例。