Разработчик тестирует модуль кэширования и хочет точно воспроизвести поведение LRU-кэша фиксированной ёмкости c.

Кэш хранит пары «ключ–значение», где и ключ, и значение — целые числа. Изначально кэш пуст.

Над кэшем выполняется последовательность из q операций двух типов:

• GET key — если ключ есть в кэше, нужно вернуть соответствующее значение. После этого элемент с данным ключом считается самым недавно использованным. Если ключа в кэше нет, нужно вернуть -1, а состояние кэша не изменяется.
• PUT key value — если ключ уже есть в кэше, его значение заменяется на value, а сам элемент становится самым недавно использованным. Если такого ключа нет, в кэш добавляется новая пара (key, value) как самый недавно использованный элемент. Если после этого размер кэша становится больше c, необходимо удалить элемент, который использовался раньше всех остальных, то есть наименее недавно использованный.

Для каждой операции GET требуется вывести результат.

После обработки всех операций выведите текущее содержимое кэша: его размер и ключи в порядке от самого недавно использованного к самому давно использованному.

Входные данные

Первая строка содержит два целых числа c и q — ёмкость кэша и количество операций.

В следующих q строках записано по одной операции в одном из форматов:

• GET key
• PUT key value

Выходные данные

Для каждой операции GET выведите в отдельной строке ответ на неё — целое число.

После всех операций выведите в отдельной строке текущее содержимое кэша: число s — текущий размер кэша, а затем через пробел s ключей в порядке от самого недавно использованного к самому давно использованному.

Ограничения

• 1 <= c <= 10^5
• 1 <= q <= 2 * 10^5
• для операции GET: -10^9 <= key <= 10^9
• для операции PUT: -10^9 <= key <= 10^9, -10^9 <= value <= 10^9

Примеры

Пример 1

Входные данные

1 8
GET 5
PUT 5 10
GET 5
PUT 6 20
GET 5
GET 6
PUT 6 -1000000000
GET 6

Выходные данные

-1
10
-1
20
-1000000000
1 6

Пример 2

Входные данные

2 12
PUT 1 10
PUT 2 20
GET 1
PUT 3 30
GET 2
GET 3
PUT 1 100
GET 1
PUT -1 -1
GET 3
GET -1
GET 2

Выходные данные

10
-1
30
100
-1
-1
-1
2 -1 1