QOJ.ac

QOJ

Time Limit: 5 s Memory Limit: 2048 MB
[+4]

# 601. 李超树

Statistics

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, output NO.

Constraints

  • 1N,Q200000
  • 109li<ri109
  • |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