407930: GYM102944 G Grand Rabbits

Feeding rabbits is never an easy job, especially when the rabbits are large. In the city of Grand Rabbits there are $$$N$$$ families of large rabbits that live along a long, straight street.

These families are numbered $$$1,2,\ldots ,N$$$ as you traverse the street. You run a carrot delivery company that delivers carrots to the rabbit families each day. Whenever you deliver to the $$$i$$$-th family on the street, you leave an order of $$$a_i$$$ pounds of carrots. You have worked out a schedule where you deliver on $$$D$$$ consecutive days. On the $$$d$$$-th day of the schedule, you deliver to the families numbered from $$$L_d$$$ to $$$R_d$$$, where $$$1 \le L_d \le R_d\le N$$$. Also on the $$$d$$$-th day of your schedule, you have $$$k_d$$$ trucks available to deliver these orders. To save wear on your trucks each day, you would like to apportion the $$$R_d - L_d + 1$$$ orders among the $$$k_d$$$ trucks so that the maximum load is minimized. Furthermore, to save gas, each truck should deliver to a set of consecutively numbered families. For example, if there are $$$10$$$ families in all, with $$$a_i=i$$$ for $$$i=1,2, \ldots ,10$$$, and on a particular day $$$d$$$, $$$L_d=1$$$, $$$R_d=6$$$ and $$$k_d=3$$$, then the first truck could deliver orders to families $$$1$$$, $$$2$$$, $$$3$$$, the second truck to families $$$4$$$,$$$5$$$, and the third truck to family $$$6$$$. The second truck has the maximum load, $$$9$$$ pounds, and this is minimal among all ways of apportioning the orders.

In the first line there are 2 integers $$$N$$$ and $$$D$$$ ($$$1\le N, D\le 10^5$$$), indicating the number of rabbit families and number of days your company runs. Then the next line contains $$$N$$$ integers $$$a_1, a_2, \ldots, a_N$$$ ($$$1\le a_i\le 10^9$$$) indicating the order sizes of rabbit families. On each of the next $$$D$$$ lines, there are 3 integers $$$L_d, R_d, k_d$$$ ($$$1\le L_d\le R_d\le N, 1\le k_d\le 10$$$), indicating the family range and the number of trucks on day $$$d$$$.

For each day $$$d=1,2,\ldots ,D$$$, please output an integer indicating the maximum load of if you apportion orders optimally.

10 4
1 2 3 4 5 6 7 8 9 10
1 6 3
3 10 3
1 10 5
1 10 10

9
19
15
10