Bài 4 : Pháo hoa (4.0 điểm)

Đêm Giao thừa năm nay, bác VCB một nghệ nhân pháo hoa lão làng muốn tạo ra màn trình diễn ánh sáng chưa từng có để chào đón năm mới. Bác VCB sở hữu một dây pháo hoa thần kì. Ban đầu, dây pháo hoa chỉ có một đốm sáng khởi nguồn mang năng lượng là \(0\). Quy trình kích hoạt dây pháo diễn ra qua \(Q\) bước, được đánh số từ \(1\) đến \(Q\). Tại bước thứ \(i\), một trong hai sự kiện sau sẽ xảy ra:

• 1 x: Bác VCB chọn một đốm mang năng lượng \(x\) đang có trên dây. Bác gắn thêm một đốm sáng mới mang năng lượng đúng bằng số thứ tự của bước hiện tại \(i\) vào phía sau đốm sáng \(x\).
• 2 x y: Bác VCB chọn hai đốm sáng mốc là \(x\) và \(y\) đang tồn tại trên dây. Tất cả các đốm sáng nằm ở giữa \(x\) và \(y\) sẽ đồng loạt nổ tung, tạo thành chùm sáng rực rỡ và sau đó biến mất vĩnh viễn khỏi dây pháo nhưng hai mốc \(x\) và \(y\) vẫn giữ nguyên. Độ rực rỡ của màn nổ này bằng tổng năng lượng của các đốm sáng vừa bị xóa.

Bạn là trợ lý đắc lực của bác VCB, hãy giúp bác tính toán độ rực rỡ của từng màn "Bùng nổ" để đảm bảo chương trình diễn ra hoàn hảo nhất nhé!

Input

Vào từ tệp văn bản FIREWORK.INP theo cấu trúc:

• Dòng đầu tiên chứa số nguyên dương \(Q\) \((1 \le Q \le 5 \times 10^5)\) là số lượng truy vấn

• \(Q\) dòng tiếp theo, dòng thứ \(i\) mô tả sự kiện ở bước thứ \(i\) theo định dạng:

• 1 x: Sự kiện loại 1 \((0 \le x < i)\)

• 2 x y: Sự kiện loại 2 \((x \neq y)\)

Output

Ghi vào tệp FIREWORK.OUT với mỗi sự kiện loại 2 hãy in ra độ rực rỡ.

Example

4
1 0
1 1
1 1
2 0 2

4

6
1 0
1 1
1 0
2 2 3
1 2
2 0 5

1
5

Scoring

• Có \(20\%\) số test ứng với \(20\%\) số điểm của bài với \(Q \le 500\);
• Có \(30\%\) số test ứng với \(30\%\) số điểm của bài với \(Q \le 5 \times 10^3\);
• Có \(20\%\) số test ứng với \(20\%\) số điểm của bài với chỉ có sự kiện loại 2;
• Có \(30\%\) số test ứng với \(30\%\) số điểm của bài không có ràng buộc gì thêm.