Giá Trị Thấp Nhất

Một tập hợp các hàm bậc nhất được duy trì trong suốt quá trình xử lý. Mỗi hàm có dạng $f(x)=a\cdot x+b$, trong đó $a$ và $b$ là các số nguyên. Ban đầu tập hợp đã có $n$ hàm.

Có $q$ thao tác được thực hiện theo thứ tự:

• $0$ $a$ $b$: thêm hàm $f(x)=a\cdot x+b$ vào tập hợp;
• $1$ $x$: tìm giá trị nhỏ nhất của $f(x)$ trong tất cả các hàm đang có.

Tập hợp luôn không rỗng khi một thao tác loại $1$ được thực hiện.

Input

• Dòng đầu chứa hai số nguyên $n$ và $q$.
• $n$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a$ và $b$, mô tả một hàm ban đầu.
• $q$ dòng cuối mô tả các thao tác theo đúng định dạng ở trên.

Output

• Với mỗi thao tác loại $1$, in ra một dòng chứa giá trị nhỏ nhất tìm được.

Constraints

• $1\le n,q\le 2\cdot 10^5$.
• $|a|,|x|\le 10^9$.
• $|b|\le 10^{18}$.
• Mọi đáp án nằm trong miền của số nguyên $64$-bit có dấu.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n,q\le 60$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

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

5
1
-5
0