가장 오래전에 접근한 페이지를 교체하는 캐시 교체 알고리즘을 구현하여 보자. 이 캐시에는 키와 값 쌍이 저장되며, 저장할 수 있는 키의 개수가 제한되어 있다. 캐시는 put(K, V), get(K) 두 개의 연산을 제공하며, 두 연산을 모두 O(1)에 제공할 수 있어야 합니다. 두 연산은 다음과 같이 동작합니다.
put(K,V): 키 값 K가 캐시에 존재하면 기존 키 값을 V로 교체함. 키가 존재하지 않으면 가장 오래전에 사용한 키 값을 (K,V)로 교체함
get(K): 키 값 K가 캐시에 존재하면 그 키에 해당하는 V값을 반환하고, 없으면 -1을 반환함

첫 줄에는 테스트케이스 T(1<=T<=100)가 주어집니다. 각 테스트케이스마다 첫 줄에는 캐시의 슬롯 수 C(1<=C<=1,000)와 명령 수 N(1<=N<=1,000)이 주어집니다. 그다음 줄에는 N개의 명령이 주어집니다. 각 명령은 0 또는 1로 시작하며, 0으로 시작하면 정수 2개가 더 주어지며, 1로 시작하면 정수 1개가 더 주어집니다. 0 다음에 주어지는 정수 2개는 캐시에 저장해야 하는 키 K(1<=K<=3,000)와 값 V(1<=V<=1,000)이며, 1 다음에 주어지는 정수 1개는 캐시에서 읽고자 하는 키 K입니다.

각 테스트케이스마다 각 명령을 차례로 실행하였을 때 명령 1들이 반환하는 값을 차례로 출력하여야 합니다. 각 값 사이에 하나의 공백이 있어야 합니다.

2 9
0 1 1 0 2 2 1 1 0 3 3 1 2 0 4 4 1 1 1 3 1 4
명령 1: 0 1 1
캐시 [(1:1),_]
명령 2: 0 2 2
캐시 [(1:1),(2:2)]
명령 3: 1 1
출력: 1
명령 4: 0 3 3 // 가장 최근에 사용한 키는 1이므로 (2:2)와 교체
캐시 [(1:1),(3:3)]
명령 5: 1 2
출력: -1
명령 6: 0 4 4 // 가장 최근에 사용한 키는 3이므로 (1:1)와 교체
캐시 [(4:4),(3:3)]
명령 7: 1 1
출력: -1
명령 8: 1 3
출력: 3
명령 9: 1 4
출력: 4
get(K), put(K,V)를 하면 K를 사용한 것임