C. Лоренцо Фон Маттерхорн
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Барни живет в Нью-Йорке. Нью-Йорк содержит бесконечное число перекрестков, пронумерованных целыми числами, начиная с 1. Известно, что в городе существует дорога, соединяющая перекрестки с номерами i и 2i, и дорога, соединяющая перекрестки с номерами i и 2i + 1, для любого целого положительного i. Все дороги в городе двусторонние. Легко убедиться, что между любыми двумя перекрестками существует ровно один кратчайший путь.

Изначально передвижение по любой дороге является бесплатным, однако, так как намечается «День пощечедавания», в ближайшее время произойдет q последовательных событий:

1. Правительство издает новое правило, определяемое тройкой целых чисел v, u и w, согласно которому стоимость передвижения по всем дорогам на кратчайшем пути от u до v увеличивается на w долларов.

2. Барни идет из перекрестка v до перекрестка u, где хочет обниматься с девушкой. Барни всегда использует кратчайший путь (по количеству посещенных вершин и дорог) для перемещения между перекрестками.

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

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

Первая строка содержит единственное целое число q (1 ≤ q ≤ 1 000).

Следующие q строк описывают происходящие события в хронологическом порядке. Каждая из следующих строк имеет вид 1 v u w и соответствует событию, когда правительство издает правило об увеличении стоимости прохождения по всем дорогам на кратчайшем пути от перекрестка u до перекрестка v на w долларов, либо имеет вид 2 v u и соответствует событию, когда Барни идет от перекрестка v до перекрестка u по кратчайшему пути.

Для всех описаний событий выполняется 1 ≤ v, u ≤ 1018, v ≠ u, 1 ≤ w ≤ 109.

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

Для каждого события второго типа выведите суммарную стоимость прохождения дорог, которые Барни пройдет на своем пути. Ответы выводите в том же порядке, что и соответствующие им запросы.

Пример
Входные данные
7
1 3 4 30
1 4 1 2
1 3 6 8
2 4 3
1 6 1 40
2 3 7
2 2 4
Выходные данные
94
0
32
Примечание

В запросах первого примера:

  1. Перекрестки на пути — 3, 1, 2 и 4.
  2. Перекрестки на пути — 4, 2 и 1.
  3. Перекрестки на пути — 3 и 6.
  4. Перекрестки на пути — 4, 2, 1 и 3. Стоимости прохождения по дорогам равны 32, 32 и 30 в порядке прохождения. Ответ равен 32 + 32 + 30 = 94.
  5. Перекрестки на пути — 6, 3 и 1.
  6. Перекрестки на пути — 3 и 7. Стоимость прохождения по дороге между ними равна 0.
  7. Перекрестки на пути — 2 и 4. Стоимость прохождения по дороге между ними равна 32 (увеличенная на 30 после первого события и на 2 после второго).