Benny and Queries
Tag(s):

## Greedy algorithm, Medium-Hard, Trie

Problem
Editorial
Analytics

Probably, you have already read some problems but you still have not met any problems with queries on segments. Therefore Benny wants to fix it.

She gives you an array A of N elements. And then you have to answer Q queries.

Each query consists of three integers L, R, X. Your task is to find such Ai, that LiR and Ai xor X is maximal. For each query output the maximum of Ai xor X.

Input format

The first line contains two integers N and Q. The next line contains N integers Ai. The next Q lines contain three integers L, R, X.

Output format

For each query output the maximum of Ai xor X in a single line.

Constraints

• 1 ≤ N, Q ≤ 5 * 105
• 0 ≤ Ai < 220
• 1 ≤ L ≤ R ≤ N
• 0 ≤ X < 220
• 1 ≤ N, Q ≤ 3 * 103 holds for test cases worth 15% of the problem's score.
• 1 ≤ N, Q ≤ 105 holds for test cases worth 60% of the problem's score.
SAMPLE INPUT
5 3
1 7 3 8 2
1 5 10
3 4 6
2 5 8

SAMPLE OUTPUT
13
14
15

Time Limit: 4.0 sec(s) for each input file.
Memory Limit: 512 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

March Easy '16

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Sorting
• Algorithms > Sorting