All Tracks Data Structures Advanced Data Structures Trie (Keyword Tree) Problem

Xor sequence
/

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

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
通知
View All Notifications

?