Marisa planted $n$ apple trees in a row. There are $q$ rainy days. On each day $i$, a certain amount of rainwater, denoted as $w_i$ liters, was received by each tree within the range $[l_i, r_i]$.
Each tree, denoted as the $i^{th}$ tree, requires a specific amount of water, denoted as $A_i$ liters, in order to undergo mutation. Marisa seeks to determine the day on which each tree mutates.
### Input
- The first line contains two integers $n,q$.
- The second line contains $n$ integer $A_i$.
- The next $q$ lines, each line three integers $l_i,r_i,w_i$.
### Output
- Print $n$ integers, the $i^{th}$ one is the day on which tree $i$ mutates. Or print `-1` if it won't mutate.
### Constraints
- $1 \le n,q \le 10^5$
- $1 \le l_i \le r_i \le n$.
- $1 \le w_i,A_i \le 10^9$.
### Example
Input:
```
5 3
3 7 2 1 6
1 5 3
2 3 2
3 5 3
```
Output:
```
1 -1 1 1 3
```
