We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Bit Manipulation
  4. Maximizing the Function

Maximizing the Function

Problem
Submissions
Leaderboard
Discussions
Editorial

Consider an array of binary integers (i.e., 's and 's) defined as .

Let be the bitwise XOR of all elements in the inclusive range between index and index in array . In other words, . Next, we'll define another function, :

Given array and independent queries, perform each query on and print the result on a new line. A query consists of three integers, , , and , and you must find the maximum possible you can get by changing at most elements in the array from to or from to .

Note: Each query is independent and considered separately from all other queries, so changes made in one query have no effect on the other queries.

Input Format

The first line contains two space-separated integers denoting the respective values of (the number of elements in array ) and (the number of queries).
The second line contains space-separated integers where element corresponds to array element .
Each line of the subsequent lines contains space-separated integers, , and respectively, describing query .

Constraints

Subtask

  • and for of the maximum score
  • , and for of the maximum score

Output Format

Print lines where line contains the answer to query (i.e., the maximum value of if no more than bits are changed).

Sample Input

3 2
0 0 1
0 2 1
0 1 0

Sample Output

4
0

Explanation

Given , we perform the following queries:

  1. If we change to , then we get and .
  2. In this query, .

Author

muratekici

Difficulty

Hard

Max Score

70

Submitted By

418

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature