Problem Setter: Emrul hasan Emon

Member, IUBAT IITS Programming Club

You are preparing to celebrate your parents' anniversary and plan to buy them a gift. You visit a renowned gift shop in Dhaka, where you find a row of N gifts, each priced at P_i. When you share the occasion with the shop owner, he is delighted and offers you a discount.

The discount works as follows: the shop owner selects a range (L to R) of gift prices, and you need to determine the binary AND of the prices within that range. If you correctly calculate this value, you can purchase the first gift within that range at the computed price. Once you make the purchase, the shop owner replaces the bought gift with another one priced at C.

Due to your busy schedule, you decide to write a program that takes a price range as input and calculates the binary AND of the prices falling within that range.

Binary and is a bitwise operation that performs a logical AND operation on each corresponding bit of two binary numbers. The result of a binary and operation is a new binary number whose corresponding bits are 1 only if both of the corresponding bits in the two input numbers are 1.

Input Format

The first line contains two integers, N (the number of gifts available in the shop) and Q (the number of queries the shop owner will make).

The second line contains N integers, prices of the gifts.

The next Q lines contain 3 integers each: L, R (denoting the inclusive range), and C (the price that will replace the gift within the range).

Constrains:

1 <= N <= 10⁵

1 <= Q <= 10⁵

1 <= Pi <= 10⁹ (price of gifts)

1 <= L <= R <= N (range inclusivity)

1 <= C <= 10⁹ (replacement price)

Output Format

For each query print the binary and of that range.

Samples