Xor sequence
Tag(s):

## Advanced Data Structures, Data Structures, Medium-Hard, Trie

Problem
Editorial
Analytics

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$

SAMPLE INPUT
5 3 0
8 6 2 4 5
0 4
0 2
2 4

SAMPLE OUTPUT
14
14
6

Explanation

The actual queries are $(1,5),(1,3),(3,5)$.

You can choose $(i,j)$ as $(1,2),(1,2),(3,4)$ to maximize the value.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 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

April Circuits '18

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Graphs
• Basic Programming > Implementation
• Math > Combinatorics
• Algorithms > Dynamic Programming
• Algorithms > Dynamic Programming