Implement an LFU (Least Frequently Used) cache of size cacheSize that supports two operations.

• GET key

  • Retrieve the value associated with key.
  • If the key is not present, return -1.

• PUT key value

  • Insert or update the (key, value) pair.
  • If the cache is full, remove the least frequently used key.
  • If multiple keys have the same frequency, remove the least recently used among them.

Return an array containing the outputs of every GET query in order.

---

Example

cacheSize = 1

queries =
["PUT 1 1",
 "PUT 2 2",
 "GET 1"]

Execution

Query	Cache	Output
PUT 1 1	{1=1}
PUT 2 2	{2=2}
GET 1	{2=2}	-1

Return

[-1]

---

Function

implementLFU(cacheSize, queries)

Parameters

int cacheSize
string queries[q]

Returns

int[]

Outputs of all GET queries.

---

Constraints

2 ≤ cacheSize ≤ 100
1 ≤ q ≤ 10^5
At least one GET query exists.
Length of query ≤ 17
Keys and values contain digits (0-9) only.
Value of key ≤ 300
Value of value ≤ 10^5

---