E. Сообщения
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп — тьютор группы из $$$n$$$ студентов. Он связывается с ними через конференцию в популярном мессенджере.

Сегодня у Монокарпа был напряженный день — его просили переслать его группе огромное количество объявлений, поэтому ему пришлось написать в конференции очень много сообщений. Монокарп достаточно хорошо знает студентов из группы, поэтому понимает, какое сообщение является важным для каждого студента: Монокарп хочет, чтобы студент $$$i$$$ прочитал сообщение $$$m_i$$$.

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

К сожалению, даже если сообщение прикреплено, некоторые студенты все равно могут его пропустить. Для каждого студента $$$i$$$ Монокарп знает, что этот студент прочитает не более $$$k_i$$$. Предположим, что Монокарп прикрепляет $$$t$$$ сообщений; если $$$t \le k_i$$$, то $$$i$$$-й студент прочитает все прикрепленные сообщения; но если $$$t > k_i$$$, $$$i$$$-й студент выберет ровно $$$k_i$$$ случайных прикрепленных сообщений (все различные подмножества размера $$$k_i$$$ множества прикрепленных сообщений равновероятны) и прочитает только их.

Монокарп хочет максимизировать математическое ожидание количества студентов, которые прочитают необходимые им сообщения (это соответствует количеству таких индексов $$$i$$$, что студент $$$i$$$ прочитает сообщение $$$m_i$$$). Помогите ему выбрать, какие сообщения прикрепить!

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

В первой строке задано одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество студентов в конференции.

Затем следуют $$$n$$$ строк. $$$i$$$-я строка содержит два целых числа $$$m_i$$$ и $$$k_i$$$ ($$$1 \le m_i \le 2 \cdot 10^5$$$; $$$1 \le k_i \le 20$$$) — номер сообщения, которое должен прочитать $$$i$$$-й студент, и максимальное кол-во сообщений, которое $$$i$$$-й студент может прочитать, соответственно.

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

В первой строке выведите одно целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — количество сообщений, которые должен прикрепить Монокарп. Во второй строке выведите $$$t$$$ различных целых чисел $$$c_1$$$, $$$c_2$$$, ..., $$$c_t$$$ ($$$1 \le c_i \le 2 \cdot 10^5$$$) — номера сообщений, которые необходимо прикрепить. Номера сообщений можно выводить в любом порядке.

Если оптимальных ответов несколько, выведите любой из них.

Примеры
Входные данные
3
10 1
10 2
5 2
Выходные данные
2
5 10
Входные данные
3
10 1
5 2
10 1
Выходные данные
1
10
Входные данные
4
1 1
2 2
3 3
4 4
Выходные данные
3
2 3 4
Входные данные
3
13 2
42 2
37 2
Выходные данные
3
42 13 37
Примечание

Рассмотрим примеры из условия.

  1. В первом примере Монокарп прикрепляет сообщения $$$5$$$ и $$$10$$$.
    • если первый студент прочитает сообщение $$$5$$$, второй студент прочитает сообщения $$$5$$$ и $$$10$$$, и третий студент прочитает сообщения $$$5$$$ и $$$10$$$, количество студентов, которые прочитают соответствующие им сообщения, будет равно $$$2$$$;
    • если первый студент прочитает сообщение $$$10$$$, второй студент прочитает сообщения $$$5$$$ и $$$10$$$, и третий студент прочитает сообщения $$$5$$$ и $$$10$$$, количество студентов, которые прочитают соответствующие им сообщения, будет равно $$$3$$$.

    Поэтому математическое ожидание количества студентов, которые прочитают соответствующие им сообщения, равно $$$\frac{5}{2}$$$.

  2. В первом примере Монокарп прикрепляет сообщение $$$10$$$.
    • если первый студент прочитает сообщение $$$10$$$, второй студент прочитает сообщение $$$10$$$, и третий студент прочитает сообщение $$$10$$$, количество студентов, которые прочитают соответствующие им сообщения, будет равно $$$2$$$.

    Поэтому математическое ожидание количества студентов, которые прочитают соответствующие им сообщения, равно $$$2$$$. Если бы Монокарп прикрепил и сообщение $$$5$$$, и сообщение $$$10$$$, математическое ожидание так же было бы равно $$$2$$$.

  3. В третьем примере математическое ожидание кол-ва студентов, которые прочитают соответствующие им сообщения, равно $$$\frac{8}{3}$$$.
  4. В четвертом примере математическое ожидание кол-ва студентов, которые прочитают соответствующие им сообщения, равно $$$2$$$.