Единственное отличие между простой и сложной версиями — ограничения на \(n\) и \(k\).
Вы общаетесь в одной из популярных социальных сетей, используя свой смартфон. Ваш смартфон может показывать не более \(k\) самых недавних бесед с вашими друзьями. Изначально экран смартфона пуст (то есть количество показанных бесед равно \(0\)).
Каждая беседа — это ваш диалог с каким-то из ваших друзей. Всего существует не более одной беседы с каждым из ваших друзей. Таким образом, каждая беседа однозначно определяется вашим другом.
Вы (внезапно!) обладаете возможностью видеть будущее. Вы знаете, что в течение дня вы получите \(n\) сообщений, \(i\)-е сообщение будет получено от друга с ID \(id_i\) (\(1 \le id_i \le 10^9\)).
Если вы получаете сообщение от друга \(id_i\) тогда, когда беседа с ним сейчас показана на экране смартфона, то ничего не происходит: беседы на экране не меняются и не меняют свой относительный порядок, вы просто читаете сообщение и продолжаете ждать новых сообщений.
Иначе (то есть тогда, когда на экране нет беседы с другом \(id_i\)):
- Сначала, если количество бесед, отображенных на экране, равно \(k\), последняя беседа (которая имеет позицию \(k\)) удаляется с экрана.
- Теперь количество бесед на экране гарантированно меньше \(k\) и беседа с другом \(id_i\) не отображена на экране.
- Беседа с другом \(id_i\) появляется на первой (верхней) позиции на экране и все другие отображенные беседы сдвигаются на одну позицию вниз.
Ваша задача — найти список бесед (в порядке, в котором они будут отображены на экране) после обработки всех \(n\) сообщений.
Выходные данные
В первой строке выходных данных выведите одно целое число \(m\) (\(1 \le m \le min(n, k)\)) — количество бесед, показанных на экране после получения всех \(n\) сообщений.
Во второй строке выходных данных выведите \(m\) целых чисел \(ids_1, ids_2, \dots, ids_m\), где \(ids_i\) должно быть равно ID друга, соответствующего беседе, отображенной на позиции \(i\) после получения всех \(n\) сообщений.
Примечание
В первом тестовом примере список бесед будет изменяться следующим образом (в порядке от первого к последнему сообщению):
- \([]\);
- \([1]\);
- \([2, 1]\);
- \([3, 2]\);
- \([3, 2]\);
- \([1, 3]\);
- \([1, 3]\);
- \([2, 1]\).
Во втором тестовом примере список бесед будет изменяться следующим образом:
- \([]\);
- \([2]\);
- \([3, 2]\);
- \([3, 2]\);
- \([1, 3, 2]\);
- и затем список не изменится до самого конца.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 2
1 2 3 2 1 3 2
|
2
2 1
|
|
2
|
10 4
2 3 3 1 1 2 1 2 3 3
|
3
1 3 2
|