Musaigen no Phantom World
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В далекой галактике существует загадочный мир, известный как «Призрачный мир». В этом мире существуют различные существа, называемые «Призрачными». Каждый Призрачный обладает уникальными способностями и приоритетом.

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

Но связи между Призрачными не так просты, как кажется. Каждая связь имеет свой приоритет, который определяет силу и значимость этой связи. Чем выше приоритет, тем сильнее связь.

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

В Призрачном мире существуют два типа запросов, которые могут быть сделаны к Высшему Разуму:

1. Запрос на добавление связи: + $$$a$$$ $$$b$$$ $$$k$$$. Этот запрос добавляет новую связь между двумя Призрачными существами с приоритетом $$$k$$$. Благодаря этому запросу, новая связь будет создана между Призрачными существами $$$a$$$ и $$$b$$$ с приоритетом $$$k$$$.

2. Запрос на поиск минимального приоритета: ? $$$p$$$. Этот запрос позволяет найти минимальный неотрицательный приоритет $$$k$$$, при котором ребра с приоритетом меньше или равном $$$k$$$, образуют ровно $$$p$$$ компонент связности в графе Призрачного мира. Если такого приоритета не существует, выводится значение $$$-1$$$.

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

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

Первая строка входных данных содержит два целых числа $$$n$$$ — количество вершин и $$$q$$$ — количество запросов ($$$1 \leq n \leq 3000$$$, $$$0 \leq q \leq 10^5$$$)

Далее в следующих $$$q$$$ строчках идет описание запросов. Описание каждого запроса имеет следующий вид:

- Запрос первого типа задается в виде: + $$$a$$$ $$$b$$$ $$$k$$$ ($$$1 \leq a,b \leq n$$$, $$$1 \leq k \leq 10^9$$$). Гарантируется, что никакие два ребра не имеют одинаковый приоритет.
- Запрос второго типа задается в виде: ? $$$p$$$ ($$$1 \leq p \leq n$$$)

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

Выведите ответ на каждый запрос второго типа

Пример

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

    6 12
    + 1 2 1
    + 1 3 3
    + 2 3 7
    + 4 5 2
    + 5 6 4
    ? 1
    + 6 3 5
    + 6 3 10
    + 6 4 6
    ? 6
    ? 2
    ? 1

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

    -1
    0
    4
    5

Примечание

Итоговый граф в примере