Lorenzo Von Matterhorn

Xét một cây nhị phân vô hạn với các đỉnh được đánh số bằng số nguyên dương bắt đầu từ $1$. Với mỗi số nguyên dương $i$, tồn tại một cạnh hai chiều giữa đỉnh $i$ và đỉnh $2i$, và một cạnh hai chiều giữa đỉnh $i$ và đỉnh $2i+1$. Giữa hai đỉnh bất kì, đường đi ngắn nhất là duy nhất.

Ban đầu mọi cạnh có phí qua đường bằng $0$. Bạn cần xử lý $q$ sự kiện theo thứ tự, mỗi sự kiện thuộc một trong hai loại:

• Loại 1: Cho ba số nguyên $v$, $u$, $w$. Phí qua đường của mọi cạnh trên đường đi ngắn nhất giữa $u$ và $v$ tăng thêm $w$.
• Loại 2: Cho hai số nguyên $v$, $u$. Hãy tính tổng phí qua đường của mọi cạnh trên đường đi ngắn nhất giữa $u$ và $v$.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $q$ — số sự kiện.
• $q$ dòng tiếp theo mô tả các sự kiện theo thứ tự. Mỗi dòng bắt đầu bằng loại sự kiện:
  • 1 v u w cho sự kiện loại 1.
  • 2 v u cho sự kiện loại 2.

Dữ liệu ra

Với mỗi sự kiện loại 2, in ra một dòng chứa tổng phí cần trả.

Ràng buộc

• $1\le q\le 1000$
• $1\le v,u\le {10}^{18}$, $v\ne u$
• $1\le w\le {10}^9$

Ví dụ