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

Бельчата решили поиграть в прятки на дереве. Правила игры просты: выбирается вершина $$$v$$$ — в ней будет находиться водящий бельчонок. Остальные бельчата разбегаются по дереву и прячутся в его вершинах. Чем дальше вершина от водящего, тем она безопаснее.

Изначально дерево состоит из единственной вершины с номером $$$1$$$. Вам нужно обрабатывать запросы двух видов:

Вершина $$$u_i$$$ в запросе $$$i$$$ вычисляется по формуле

$$$$$$u_i = (ans_{i-1}\cdot m + v_i - 1) \bmod sz + 1$$$$$$

где $$$ans_{i-1}$$$ — сумма наибольшего расстояния и количества вершин из ответа на предыдущий запрос типа $$$?$$$ (положим $$$ans_{0} = 0$$$), $$$v_i$$$ — параметр запроса из ввода, $$$sz$$$ — текущий размер дерева.

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

В первой строке ввода находятся два целых числа $$$q$$$ и $$$m$$$ — количество запросов и флаг, отвечающий за генерацию запросов $$$(1 \leq q \leq 300\,000, m \in \{0,1\})$$$.

В следующих $$$q$$$ строках находятся сами запросы в соответствии с форматом, описанным в условии, по одному в строке. Гарантируется, что $$$0 \leq v_i \leq q$$$.

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

В ответ на каждый запрос второго типа выведите на отдельной строке два числа, разделенные пробелом — расстояние от вершины $$$u_i$$$ до самой дальней от нее вершины дерева, а также количество вершин на таком расстоянии от $$$u_i$$$.

Система оценки

В задаче 28 тестов (помимо тестов из условия), оценка потестовая. Тесты задачи можно разбить на следующие подгруппы:

|c|}

Макс. Балл

$$$m$$$ Дополнительные Ограничения Комментарий
0тест из условия
9$$$m=0$$$ $$$q\leq 100$$$
20$$$m=0$$$ все запросы типа + идут до всех запросов типа ?
8$$$m=0$$$ диаметр итогового дерева не превосходит $$$50$$$
16$$$m=1$$$ в запросах типа ? $$$u_i=1$$$ (после пересчета по формуле)
20$$$m=1$$$ в запросах типа ? $$$u_i=1$$$ или $$$u_i$$$ — сосед вершины $$$1$$$ (после пересчета по формуле)
15$$$m=0$$$
12$$$m=1$$$

Примеры

Входные данные
10 0
+ 1
? 2
+ 2
? 2
+ 3
? 2
+ 4
? 1
+ 4
? 1
Выходные данные
1 1
1 2
2 1
4 1
4 2
Входные данные
10 1
+ 1
? 1
+ 1
+ 0
+ 0
+ 1
+ 1
? 1
? 5
? 2
Выходные данные
1 1
3 2
3 2
4 2

Примечание

Во втором тесте из условия значения $$$u_i$$$ (после пересчета по формуле) следующие: $$$[1,1,1,2,2,3,3,3,3,7]$$$.

Также приведем итоговое дерево из первого примера: