#### Gift Shop

**Author: ** Efat Sikder

Problem Setter:Emrul hasan EmonMember, IUBAT IITS Programming Club

You are preparing to celebrate your ** parents' anniversary** and plan to buy them a

**. You visit a renowned**

*gift***shop in**

*gift***, where you find a row of**

*Dhaka***N**gifts, each priced at

**. When you share the**

*P*_{i}*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

**of the prices within that range. If you correctly calculate this value, you can purchase the first gift within that range at the**

*binary AND***. Once you make the purchase, the shop owner replaces the bought gift with another one priced at**

*computed price***.**

*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 ^{5}*

*1 <= Q <= 10 ^{5}*

*1 <= Pi <= 10 ^{9} (price of gifts)*

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

*1 <= C <= 10 ^{9} (replacement price)*

#### Output Format

For each query print the binary and of that range.

Print a new line after printing all queries.#### Samples

###### Input

###### Output

###### Input

###### Output

Language | Time | Memory |

GNU C 11 | 1s | 512MB |

GNU C++ 14 | 1s | 512MB |

GNU C++ 11 | 1s | 512MB |

PHP 7 | 1s | 1024MB |

Java (OpenJDK 8) | 1s | 4096MB |