Барни живет в Нью-Йорке. Нью-Йорк содержит бесконечное число перекрестков, пронумерованных целыми числами, начиная с 1. Известно, что в городе существует дорога, соединяющая перекрестки с номерами i и 2i, и дорога, соединяющая перекрестки с номерами i и 2i + 1, для любого целого положительного i. Все дороги в городе двусторонние. Легко убедиться, что между любыми двумя перекрестками существует ровно один кратчайший путь.
Изначально передвижение по любой дороге является бесплатным, однако, так как намечается «День пощечедавания», в ближайшее время произойдет q последовательных событий:
1. Правительство издает новое правило, определяемое тройкой целых чисел v, u и w, согласно которому стоимость передвижения по всем дорогам на кратчайшем пути от u до v увеличивается на w долларов.
2. Барни идет из перекрестка v до перекрестка u, где хочет обниматься с девушкой. Барни всегда использует кратчайший путь (по количеству посещенных вершин и дорог) для перемещения между перекрестками.
Теперь правительству нужна ваша помощь: каждый раз, когда Барни отправляется обниматься с девушкой, вам нужно сообщать, сколько долларов Барни должен заплатить (т.е. суммарную стоимость передвижения по всем дорогам, которые он пройдет).
Выходные данные
Для каждого события второго типа выведите суммарную стоимость прохождения дорог, которые Барни пройдет на своем пути. Ответы выводите в том же порядке, что и соответствующие им запросы.