The Coastal Thieves Problem

There is a row of houses along a coastline numbered from 1 to n. The i-th house contains \(a_i\) coins. There are m thieves, and the i-th thief starts with \(c_i\) coins. Thief i will rob houses sequentially from house \(l_i\) to \(r_i\).

For each house j the thief visits, let his current coin count be \(k\). The following rules are applied:

• If \(k < a_j\), he steals 1 coin (i.e. \(k \gets k+1\)).
• If \(k = a_j\), nothing happens.
• If \(k > a_j\), he gives 1 coin to the homeowner (i.e. \(k \gets k-1\)).

Each thief's robbery is independent. That is, after a thief finishes, the houses are restored to their original coin amounts for the next thief. Your task is to determine the final coin count for each thief after his robbery.

inputFormat

The input consists of several lines:

The first line contains two integers \(n\) and \(m\) \( (1 \leq n, m \leq \text{some bound})\) -- the number of houses and the number of thieves respectively.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) representing the coins in each house.

Then m lines follow. The i-th of these lines contains three integers \(l_i, r_i, c_i\) \( (1 \leq l_i \leq r_i \leq n)\) where \(l_i\) and \(r_i\) denote the range of houses the i-th thief robs, and \(c_i\) is his initial coin count.

outputFormat

For each thief, output a single line containing the final number of coins in his bag after he has attempted to rob all houses in his designated range.

sample

5 3
3 3 2 4 5
1 3 2
2 5 3
1 5 6

2
4
5