All Tracks Problem

Benny and Queries
Tag(s):

Greedy algorithm, Medium-Hard, Trie

Problem
Editorial
Analytics

View Russian Translation

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...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

March Easy '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?