Катя собирается поехать в другой город на сборы по программированию и, конечно, самое главное в этом вопросе – это собрать чемодан. Набор одежды Кати состоит из футболки и джинсов. Катя знает, что сборы продлятся $$$k$$$ дней и планирует положить в чемодан $$$n$$$ футболок и $$$m$$$ джинсов. Заметим, что ещё один дополнительный комплект одежды будет надет на Кате во время поездки.

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

Удастся ли Кате добиться желаемого?

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

Когда Катя берёт в руки очередную футболку, она действует так: если футболка с таким же номером не была встречена Катей ранее – она покупает текущую футболку, в противном случае Катя переходит к следующей футболке без покупки.

Помогите Кате определить, какие футболки ей стоит купить в соответствии с её правилами.

Недавно Ваня накопил $$$k$$$ монет и теперь хочет потратить их на покупку тетрадок в клеточку. Ему известна информация про $$$n$$$ магазинов: а именно, ему известно $$$n$$$ пар чисел ($$$a_i$$$, $$$b_i$$$), где $$$a_i$$$ означает цену тетрадки в клеточку в $$$i$$$-м магазине, а $$$b_i$$$ означает количество тетрадей в клеточку, имеющихся в наличии в этом магазине.

Какое максимальное число тетрадей в клеточку может купить Ваня?

Маг Чариотис занимается выращиванием тыкв. Размер тыквы определяется целым числом (объёмом в кубических метрах).

У мага есть три заклинания: первое увеличивает размер любой тыквы на $$$p$$$, второе увеличивает размер любой тыквы в $$$k$$$ раз, а третье превращает тыкву размера ровно $$$m$$$ в карету (на тыквы других размеров оно не оказывает никакого влияния).

Изначально у мага есть $$$n$$$ тыкв и он планирует сделать как можно больше карет. Чтобы не колдовать попусту, ему хочется узнать, из каких тыкв возможно получить кареты, пользуясь только заклинаниями.

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

Обратите внимание, что ограничения на $$$a_i$$$ и $$$b_i$$$ отличаются от ограничений в задаче $$$C$$$!

Помогите Ване справиться с новыми трудностями!

В сказочной стране Айландлэнде правит добрый и мудрый король.

На данный момент, Айландлэнд состоит из $$$n$$$ островов, пронумерованных числами от $$$1$$$ до $$$n$$$, на каждом из которых живут жители. Никакие два острова не связаны между собой мостами, поэтому жителям приходится добираться от одного острова до другого вплавь.

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

Король решил начать строить мосты между островами, но строительство мостов - дело достаточно непредсказуемое. Король получает донесения двух видов:

1) В донесении первого вида сообщается, что между островами $$$u_i$$$ и $$$v_i$$$ удалось построить мост. Движение по мосту возможно в обоих направлениях.

2) В донесении второго вида сообщается, что на острове $$$u_i$$$ произошло наводнение и все его жители (если они были) переселились на остров $$$v_i$$$.

Таким образом, каждое донесение задаётся тремя параметрами: своим типом и упорядоченной парой островов.

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

Обратите внимание, что в задаче требуется ввести много данных!