E. Divide
time limit per test
6 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given an integer sequence $$$a_1,a_2,\ldots,a_n$$$ of length $$$n$$$. For an interval $$$a_l,\ldots,a_r$$$ in this sequence, a Reduce operation divides the maximum value of the interval by $$$2$$$ (rounding down). If there are multiple maximum values, choose the one with the smallest index. There are $$$q$$$ queries. Given three integers $$$l,r,k$$$ each time, query the maximum value of the interval after performing $$$k$$$ Reduce operations on the $$$a_l,\ldots,a_r$$$ interval. The queries are independent of each other. That is to say, each time the query starts from the initially given sequence.

Input

The two integers $$$n,q$$$ ($$$1\le n,q\le 10^5$$$) in the first line represent the sequence length and the number of queries.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0\le a_i\le 10^5$$$).

The next $$$q$$$ lines each have three integers $$$l,r,k$$$ ($$$1\le l\le r\le n,0\le k\le 10^9$$$), representing a query.

Output

For each query, output an integer in one line, representing the maximum value of the interval since the operation started from the initial sequence.

Examples
Input
3 2
2 0 2
2 3 0
1 3 0
Output
2
2
Input
6 6
9 5 0 3 6 7
1 4 7
3 3 233
6 6 0
3 4 4
4 5 15
1 1 0
Output
1
0
7
0
0
9