В колледже учатся \(n\) студентов, также в колледже есть \(m\) клубов, пронумерованных от \(1\) до \(m\). У каждого студента известен его потенциал \(p_i\) и номер клуба \(c_i\), членом которого он является. Изначально каждый студент является членом ровно одного клуба. Скоро в колледже состоится технический фестиваль, который продлится \(d\) дней. Каждый день в рамках фестиваля будет проведено соревнование по программированию.
Каждый день утром, ровно один студент решает покинуть свой клуб. После того как студент покинул свой клуб, он больше не присоединится ни к какому клубу снова. Каждый день в полдень, директор колледжа выбирает по одному студенту из каждого клуба (в случае если в каком-то клубе нет ни одного студента, из этого клуба не будет выбран никто) и составляет из них команду на этот день. Силой команды называется mex потенциалов студентов, которые в неё входят. Директор хочет выяснить наибольшую возможную силу команды в каждый из следующих \(d\) дней. Таким образом, каждый день директор выбирает команду так, чтобы максимизировать силу команды. Для мультимножества \(S\), его mex определён как наименьший неотрицательный элемент не входящий в \(S\). Например, mex мультимножества \(\{0, 1, 1, 2, 4, 5, 9\}\) равн \(3\), mex мультимножества \(\{1, 2, 3\}\) равен \(0\), а mex \(\varnothing\) (пустого множества) равен \(0\).
Выходные данные
Для каждого из \(d\) дней, выведите наибольшую возможную силу команды в этот день.
Примечание
Рассмотрим первый пример:
В первый день студент \(3\) покидает свой клуб. Теперь, остались студенты \(1\), \(2\), \(4\) и \(5\). Мы можем выбрать студентов \(1\), \(2\) и \(4\) чтобы получить максимальную силу команды, равную \(3\). Заметим, что мы не можем выбрать команду из студентов \(1\), \(2\) и \(5\), так как студенты \(2\) и \(5\) состоят в одном клубе. Также мы не можем выбрать команду \(1\), \(3\) и \(4\), так как студент \(3\) уже покинул свой клуб.
Во второй день студент \(2\) покидает свой клуб. Теперь, остались студенты \(1\), \(4\) и \(5\). Мы можем выбрать студентов \(1\), \(4\) и \(5\) чтобы получить максимальную возможную силу, то есть \(1\).
В третий день, остаются только студенты \(1\) и \(5\). Мы можем выбрать студентов \(1\) и \(5\) чтобы получить наибольшую возможную силу команды, то есть \(1\).
В четвёртый день, остался только студент \(1\). Мы можем выбрать студента \(1\), чтобы получить максимальную возможную силу команды, то есть \(1\).
В пятый день не осталось ни одного клуба, в котором бы состоял хотя бы один студент, а значит максимальная возможная сила равна \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3
0 1 2 2 0
1 2 2 3 2
5
3
2
4
5
1
|
3
1
1
1
0
|
|
2
|
5 3
0 1 2 2 1
1 3 2 3 2
5
4
2
3
5
1
|
3
2
2
1
0
|
|
3
|
5 5
0 1 2 4 5
1 2 3 4 5
4
2
3
5
4
|
1
1
1
1
|