Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P174PROG - ROUND 4G - Truy vấn trên đồ thị

Đồ thị G gồm các đỉnh được đánh số bằng các số nguyên dương từ 1. Mỗi đỉnh thứ i của đồ có cạnh nối 2 chiều đến các đỉnh i + i và i + i + 1. Ta định nghĩa đường đi ngắn nhất từ u đến v là đường đi từ u đến v và có tổng số lượng các cạnh ít nhất. Ban đầu trọng số của tất cả các cạnh đều bằng 0. Có 2 loại truy vấn:

  • Truy vấn 1: Tăng trọng số tất cả các cạnh thuộc đường đi ngắn nhất từ đỉnh u tới đỉnh v một giá trị w.
  • Truy vấn 2: Tìm tổng trọng số của đường đi ngắn nhất từ đỉnh u đến đỉnh v.

Input

Dòng đầu tiên gồm 1 số nguyên dương q (0 < q < 1 001) – số lượng truy vấn.

q dòng tiếp theo gồm các truy vấn, truy vấn loại 1 có dạng: 1 u v w (0 < u < v < 10 ^ 18 + 1, 0 < w < 10 ^ 9) có nghĩa trọng số mỗi cạnh thuộc đường đi ngắn nhất từ u đến v tăng lên 1 lượng giá trị w, truy vấn loại 2 có dạng 2 u v (0 < u < v < 10 ^ 18 + 1) có nghĩa cần đưa ra giá trị tổng trọng số của đường đi ngắn nhất từ u tới v. Các số u, v, w đếu là số nguyên.

Output

Với mỗi truy vấn loại 2, in ra đáp án của truy vấn, mỗi đáp án in trên 1 dòng.

Example

Input:
8
1 11 4 7
2 9 12
2 7 1
2 3 11
2 7 9
1 12 5 7
1 8 6 7
2 11 2
Output:
7
0
14
7
21 


Được gửi lên bởi:adm
Ngày:2017-03-10
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.