Задача M. Призовые места ≡

Условие

При проведении конкурса творческих работ возникла необходимость в разработке онлайн-системы подсчета голосов.

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

Полагается, что изначально всем участникам присваивается ноль баллов. Далее за каждый отданный голос участнику начисляется по одному дополнительному баллу.

За нарушение правил могут начисляться штрафы (отрицательные баллы), размер которых по абсолютной величине никогда не превосходит числа имеющихся баллов.

При формировании рейтинга среди участников, имеющих равное количество баллов, на переднее место перемещается тот, за кого проголосовали в последнюю очередь.

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

Формат входного файла

В начале входного файла "input.txt" указано общее число участников n и количество поступающих запросов m.

Далее следует ровно m таких запросов, представленных в виде пар целых чисел: a_i — номер участника; b_i — начисленные баллы/штрафы.

При этом полагается, что нумерация участников начинается с нуля.

Формат выходного файла

Выходной файл "output.txt" должен содержать результаты выполнения каждого отдельного запроса, записанные в следующем виде.

Вначале указывается число доступных призовых мест (не более трех).

Далее записываются номера соответствующих им участников.

Ограничения

0 < n ≤ 10⁵, 0 < |b_i| ≤ 1000, 0 < m ≤ 2 ⋅ 10⁵.

Примеры тестов

10
8
6 23
0 17
1 20
4 50
1 3
0 6
1 27
0 39

1 6
2 6 0
3 6 1 0
3 4 6 1
3 4 1 6
3 4 0 1
3 1 4 0
3 0 1 4

10
8
4 70
9 56
9 47
4 2
9 -31
9 -72
4 -72
7 13

1 4
2 4 9
2 9 4
2 9 4
2 4 9
1 4
0
1 7