E. Поставки золота
ограничение по времени на тест
4.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задано корневое дерево. Каждая вершина дерева содержит $$$a_i$$$ тонн золота, стоящее $$$c_i$$$ за тонну. Первоначально, дерево состоит только из корня с номером $$$0$$$, в котором $$$a_0$$$ тонн золота с ценой $$$c_0$$$ за тонну.

Всего есть $$$q$$$ запросов. Каждый запрос одного из двух видов:

  1. Подвесить вершину $$$i$$$ (где $$$i$$$ — это номер запроса) за некоторую вершину $$$p_i$$$; вершина $$$i$$$ будет содержать $$$a_i$$$ тонн золота с ценой $$$c_i$$$ за тонну. Гарантируется, что $$$c_i > c_{p_i}$$$.
  2. Для заданной вершины $$$v_i$$$ рассмотрим простой путь от $$$v_i$$$ к корню. Нам нужно приобрести $$$w_i$$$ тонн золота из вершин на этом пути, потратив наименьшее количество денег. Если на этом пути недостаточно золота, мы покупаем все что можно.

Если мы покупаем $$$x$$$ тон золота в некоторой вершине $$$v$$$, то оставшееся количество золота в ней уменьшается на $$$x$$$ (очевидно, мы не можем купить больше золота, чем есть в вершине на данный момент). Для каждого запроса второго вида посчитайте, сколько тонн золота мы купим в результате и сколько мы на это потратим.

Заметим, что вы должны решить данную задачу в онлайне. То есть вы не можете считать все входные данные заранее. Вы можете считать очередной запрос только после того как выведете ответ на предыдущий, поэтому не забывайте сбрасывать поток вывода после вывода ответа. Вы можете использовать такие функции как fflush(stdout) в C++, BufferedWriter.flush в Java или похожие после каждого вывода в программе. По стандарту (если вы не модифицировали I/O), endl сбрасывает cout в C++, а System.out.println в Java (или println в Kotlin) сбрасывают поток вывода автоматически.

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

В первой строке заданы три целых числа $$$q$$$, $$$a_0$$$ и $$$c_0$$$ ($$$1 \le q \le 3 \cdot 10^5$$$; $$$1 \le a_0, c_0 < 10^6$$$) — количество запросов, количество золота в корне и его цена за тонну.

В следующих $$$q$$$ строках заданы описания запросов: $$$i$$$-й запрос имеет один из следующих видов:

  • «$$$1$$$ $$$p_i$$$ $$$a_i$$$ $$$c_i$$$» ($$$0 \le p_i < i$$$; $$$1 \le a_i, c_i < 10^6$$$): подвесить вершину $$$i$$$ за вершину $$$p_i$$$. Вершина $$$i$$$ будет содержать $$$a_i$$$ тонн золота по цене $$$c_i$$$ за тонну. Гарантируется, что вершина $$$p_i$$$ существует и $$$c_i > c_{p_i}$$$.
  • «$$$2$$$ $$$v_i$$$ $$$w_i$$$» ($$$0 \le v_i < i$$$; $$$1 \le w_i < 10^6$$$): приобрести $$$w_i$$$ тонн золота из вершин на пути из $$$v_i$$$ в $$$0$$$, потратив минимальное количество денег. Если на пути золота недостаточно, мы покупаем все что есть. Гарантируется, что вершина $$$v_i$$$ существует.

Гарантируется, что есть хотя бы один запрос второго типа.

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

Для каждого запроса второго вида, выведите сколько тонн золота мы смогли купить и сколько на это потратили.

Пример
Входные данные
5 5 2
2 0 2
1 0 3 4
2 2 4
1 0 1 3
2 4 2
Выходные данные
2 4
4 10
1 3
Примечание

Рассмотрим пример:

В первом запросе, дерево состоит только из корня, поэтому мы приобретаем $$$2$$$ тонны золота и платим $$$2 \cdot 2 = 4$$$. В корне осталось $$$3$$$ тонны.

Во втором запросе, вы подвешиваем вершину $$$2$$$ за вершину $$$0$$$. В вершине $$$2$$$ сейчас $$$3$$$ тонны золота по цене $$$4$$$ за тонну.

В третьем запросе, простой путь из $$$2$$$ в $$$0$$$ содержит только вершины $$$0$$$ и $$$2$$$, а так как $$$c_0 < c_2$$$, мы покупаем оставшиеся $$$3$$$ тонны золота в вершине $$$0$$$ и $$$1$$$ тонну в вершине $$$2$$$. Таким образом, мы приобрели $$$3 + 1 = 4$$$ тонны и заплатили $$$3 \cdot 2 + 1 \cdot 4 = 10$$$. Теперь, вершина $$$0$$$ осталась без золота, а вершине $$$2$$$ осталось $$$2$$$ тонны золота.

В четвертом запросе, мы подвешиваем вершину $$$4$$$ за вершину $$$0$$$. В вершине $$$4$$$ сейчас $$$1$$$ тонна золота по цене $$$3$$$.

В пятом запросе, простой путь из $$$4$$$ в $$$0$$$ состоит только из вершин $$$0$$$ и $$$4$$$. Но так как в вершине $$$0$$$ уже нет золота, а в вершине $$$4$$$ только $$$1$$$ тонна, то мы покупаем $$$1$$$ тонну из вершины $$$4$$$ и тратим $$$1 \cdot 3 = 3$$$. Теперь в вершине $$$4$$$ больше не осталось золота.