Hàm Trên Nửa Khoảng

Mỗi đối tượng gồm một nửa khoảng số nguyên $[l,r)$ và một hàm bậc nhất $f(x)=a\cdot x+b$. Hàm chỉ được sử dụng tại những hoành độ thỏa $l\le x<r$.

Ban đầu có $n$ đối tượng. Sau đó, $q$ thao tác được thực hiện theo thứ tự:

• $0$ $l$ $r$ $a$ $b$: thêm hàm $a\cdot x+b$ có hiệu lực trên $[l,r)$;
• $1$ $x$: tìm giá trị nhỏ nhất tại $x$ trong các hàm có miền hiệu lực chứa $x$.

Nếu không có hàm nào có hiệu lực tại hoành độ truy vấn, hãy in INFINITY.

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 $l$ $r$ $a$ $b$, mô tả một đối tượng 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 giá trị nhỏ nhất tìm được hoặc chuỗi INFINITY.

Constraints

• $0\le n\le 2\cdot 10^5,1\le q\le 2\cdot 10^5$.
• Với mọi đoạn: $-10^9\le l<r\le 10^9$.
• $|a|,|b|,|x|\le 10^9$.
• Mọi giá trị hữu hạn cần in nằm trong miền 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

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

3
INFINITY
6
4