Xor sequence
Practice
3.4 (5 votes)
Advanced data structures
Data structures
Medium
Tries
Problem
53% Success 1343 Attempts 50 Points 2s Time Limit 256MB Memory 1024 KB Max Code

Given a sequence \(a_1{\dots}a_n\). You need to perform m queries on it.

In each query, two parameters \(x,y\) are given, and we let

\(l=min(((x+ans\cdot t)\mod n) + 1,((y+ans\cdot t)\mod n)+1)\\ r=max(((x+ans\cdot t)\mod n)+1,((y+ans\cdot t)\mod n)+1)\)

In this statement, t is a given constant, which can be 0 or 1. And \(ans\) is the answer of last query, with initial value is 0.

You need to find a pair \((i,j)\), satisfies \(l\le i\le j\le r\), and maximize \(a_i\ xor\ a_{i+1}\ xor\dots xor\ a_j\).

The answer of this query is \(a_i\ xor\ a_{i+1}\ xor\dots xor\ a_j\).

Input

The first line contains three integers, n, m, and t.

The second line contains n integers, representing the sequence a.

The next m lines, each line contains two integers, x and y.

Output

For each query, output an integer represents the answer.

Constraints

\(1\le n,m\le 20000\)

\(0\le t\le 1\)

\(0\le x,y,a_i\le 10^9\)

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:50
15 votes
Tags:
MathMedium
Points:50
43 votes
Tags:
AlgorithmsData StructuresMediumMeet-in-the-middleTries
Points:50
3 votes
Tags:
ApprovedCircuitsData StructuresMediumTries