Бельчата решили поиграть в прятки на дереве. Правила игры просты: выбирается вершина $$$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]$$$.
Также приведем итоговое дерево из первого примера: