Source: Library Checker
There are N segments y=aix+bi (where x∈[li,ri)). Process Q queries.
0 $l$ $r$ $a$ $b$
: Add a segment y=ax+b (where x∈[l,r))1 $p$
: Find the minimal y at x=p. If such y doesn't exist, outputNO
.
Constraints
- 1≤N,Q≤200000
- −109≤li<ri≤109
- |ai|,|p|≤109
- |bi|≤1018
Input
$N$ $Q$ $l_0$ $r_0$ $a_0$ $b_0$ $l_1$ $r_1$ $a_1$ $b_1$ : $l_{N-1}$ $r_{N-1}$ $a_{N-1}$ $b_{N-1}$ $\textrm{Query}_0$ $\textrm{Query}_1$ : $\textrm{Query}_{Q - 1}$
Examples
Input 1
2 8
-3 3 -1 -1
0 7 0 1
1 -1
1 -2
1 0
1 2
0 -4 2 0 -10
1 -2
1 0
1 2
Output 1
0
1
-1
-3
-10
-10
-3
Input 2
1 2
-10 0 0 0
1 0
1 -1
Output 2
NO
0