Design and implement a data structure for Least Recently Used(LRU) cache.

Problem Note:

• The LRU Cache is initialized with a positive capacity
• Your data structure must support two operations: get() and put()
• get(key): finds and returns the value if the key exists in the cache
• If the key is not present in the cache, get(key) returns -1
• put(key, value): inserts new key if it is not present in the cache. If the cache is filled to capacity, it must remove the least recently used entry
• Try implementing both operations in O(1) time complexity
• Input in this problem would be a series of function calls to get() and put()

Example

cache = LRUCache(3)
cache.put(1,1)
cache.put(2,2)
cache.put(1,3)
cache.get(1)    ---> returns 3
cache.put(3,4)
cache.put(4,3)  // removes key 2
cache.get(2)    ---> returns -1

Input Format:

• First-line contains N and C, the total number of queries and the cache size.
• Each of the following N lines has a query of either type 1(put) or type 2(get).
• The query of type 1 is of format: 1 k v, where k is key and v is value
• Query of type 2 is of format: 2 k, where k is key whose value is to be fetched.

For example, the input for the above example will be:

7 3
1 1 1
1 2 2
1 1 3
2 1
1 3 4
1 4 3
2 2