Điểm Cân Bằng

Ban đầu hàm $f(x)$ bằng $0$ trên mọi số nguyên. Thực hiện lần lượt các truy vấn cộng $|x-a|+b$ vào hàm hoặc hỏi số nguyên nhỏ nhất làm hàm đạt giá trị nhỏ nhất cùng giá trị nhỏ nhất ấy.

Input

• Dòng đầu chứa số truy vấn $Q$.
• Mỗi truy vấn là $1$ $a$ $b$ hoặc $2$; truy vấn đầu tiên luôn thuộc loại $1$.

Output

• Với mỗi truy vấn loại $2$, in $x$ $f(x)$, trong đó $x$ là số nguyên nhỏ nhất đạt cực tiểu.

Constraints

• $1\le Q\le 2\cdot 10^5$.
• $-10^9\le a,b\le 10^9$.
• Truy vấn đầu tiên có dạng $1$ $a$ $b$.
• Các trường hợp ngữ nghĩa quan trọng:
  • $C_{01}$: Chỉ có một điểm được thêm rồi truy vấn. Điểm đó là nghiệm và hằng $b$ là giá trị nhỏ nhất.
  • $C_{02}$: Nhiều điểm trùng nhau. Trung vị và tổng độ lệch phải xử lý đúng số lần lặp.
  • $C_{03}$: Có cả $b$ âm và dương. Các hằng số chỉ thay đổi giá trị cực tiểu, không đổi vị trí.
  • $C_{04}$: Số điểm chẵn tạo một đoạn nghiệm. Phải in đầu trái, tức số nguyên nhỏ nhất của đoạn nghiệm.

Scoring

• Subtask $1$ ($50$ điểm): $10$ test đầu có kích thước nhỏ, phù hợp với lời giải vét cạn mô tả trong tài liệu.
• Subtask $2$ ($50$ điểm): Không có giới hạn bổ sung.

Example

5
1 4 3
1 8 -1
2
1 2 5
2

4 6
4 13