#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/maang/problems/0E

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/maang/problems/0E

Repovive

Best Coupon Price - MAANG Problems | Repovive | Repovive

Back

Code

Upload

Submissions

Learn

MAANG0E. Best Coupon Price

100 ptstype :zen to enter zen mode

Time: 2sMemory: 256 MB

You are given $N$ products with prices $P_0, P_1, \ldots, P_{N-1}$ and $M$ discount coupons. Each coupon $j$ is described by three integers $(t_j,\; a_j,\; m_j)$ :

Type 0 (fixed discount): the product costs $\max(0,\; P_i - a_j)$ .
Type 1 (percentage discount): the product costs $\max\!\bigl(0,\; P_i - \lfloor a_j \cdot P_i / 100 \rfloor\bigr)$ .
Type 2 (fixed final price): the product costs $\max(0,\; a_j)$ , regardless of the original price.

A coupon $j$ may only be applied to product $i$ when $P_i \ge m_j$ (the minimum-price requirement). You may apply at most one coupon per product.

For each product, determine the lowest possible price after optimally choosing a coupon (or choosing none at all).

Constraints

$1 \le N \le 200{,}000$
$1 \le M \le 200{,}000$
$1 \le P_i \le 10^{9}$
$t_j \in \{0, 1, 2\}$
$0 \le a_j \le 10^{9}$ for types 0 and 2; $\;0 \le a_j \le 100$ for type 1
$0 \le m_j \le 10^{9}$

Input

\begin{array}{l} N \quad M \\ P_0 \quad P_1 \quad \cdots \quad P_{N-1} \\ t_0 \quad a_0 \quad m_0 \\ t_1 \quad a_1 \quad m_1 \\ \vdots \\ t_{M-1} \quad a_{M-1} \quad m_{M-1} \end{array}

Output

$R_0 \quad R_1 \quad \cdots \quad R_{N-1}$

Samples

Input

Explanation

Product 0 (price 100): coupon 0 gives $\max(0, 100-30)=70$ , coupon 1 gives $\max(0, 100-\lfloor 50 \cdot 100/100 \rfloor)=50$ , coupon 2 requires $m=150$ so it is not applicable. Best: 50.

Product 1 (price 200): coupon 0 gives $170$ , coupon 1 gives $100$ , coupon 2 gives $60$ . Best: 60.

Product 2 (price 50): all coupons require $m \ge 80$ , none applicable. Best: 50.

Output

50 60 50

Input

1 1
500
1 25 100

Explanation

Product 0 (price 500): the only coupon gives $500 - \lfloor 25 \cdot 500/100 \rfloor = 500 - 125 = 375$ . Best: 375.

Output

Input

Explanation

Product 0 (price 10): coupon 0 gives $\max(0, 10-50)=0$ , coupon 1 requires $m=15$ so not applicable. Best: 0.

Product 1 (price 20): coupon 0 gives $\max(0, 20-50)=0$ , coupon 1 gives $15$ . Best: 0.

Output

0 0

You are given $N$ products with prices $P_0, P_1, \ldots, P_{N-1}$ and $M$ discount coupons. Each coupon $j$ is described by three integers $(t_j,\; a_j,\; m_j)$ :

Type 0 (fixed discount): the product costs $\max(0,\; P_i - a_j)$ .
Type 1 (percentage discount): the product costs $\max\!\bigl(0,\; P_i - \lfloor a_j \cdot P_i / 100 \rfloor\bigr)$ .
Type 2 (fixed final price): the product costs $\max(0,\; a_j)$ , regardless of the original price.

A coupon $j$ may only be applied to product $i$ when $P_i \ge m_j$ (the minimum-price requirement). You may apply at most one coupon per product.

For each product, determine the lowest possible price after optimally choosing a coupon (or choosing none at all).

Constraints

$1 \le N \le 200{,}000$
$1 \le M \le 200{,}000$
$1 \le P_i \le 10^{9}$
$t_j \in \{0, 1, 2\}$
$0 \le a_j \le 10^{9}$ for types 0 and 2; $\;0 \le a_j \le 100$ for type 1
$0 \le m_j \le 10^{9}$

\begin{array}{l} N \quad M \\ P_0 \quad P_1 \quad \cdots \quad P_{N-1} \\ t_0 \quad a_0 \quad m_0 \\ t_1 \quad a_1 \quad m_1 \\ \vdots \\ t_{M-1} \quad a_{M-1} \quad m_{M-1} \end{array}

$R_0 \quad R_1 \quad \cdots \quad R_{N-1}$

Product 0 (price 100): coupon 0 gives $\max(0, 100-30)=70$ , coupon 1 gives $\max(0, 100-\lfloor 50 \cdot 100/100 \rfloor)=50$ , coupon 2 requires $m=150$ so it is not applicable. Best: 50.

Product 1 (price 200): coupon 0 gives $170$ , coupon 1 gives $100$ , coupon 2 gives $60$ . Best: 60.

Product 2 (price 50): all coupons require $m \ge 80$ , none applicable. Best: 50.

Product 0 (price 500): the only coupon gives $500 - \lfloor 25 \cdot 500/100 \rfloor = 500 - 125 = 375$ . Best: 375.

Product 0 (price 10): coupon 0 gives $\max(0, 10-50)=0$ , coupon 1 requires $m=15$ so not applicable. Best: 0.

Product 1 (price 20): coupon 0 gives $\max(0, 20-50)=0$ , coupon 1 gives $15$ . Best: 0.