Background

It is indeed special, indeed eye-catching, but anomalies are never truly special.

In the end, they are merely errors: echoes of the fragile parts of the human heart, possessing the timbre of a heart when its wishes are shattered.

By their very nature, they are closer to what that heart truly is than what it longs for: not special at all, but the ordinary can also possess a destructive power.

Fate itself does not bring flaws, and such pain cannot be escaped through hope or the threads of fate—in this regard, the fact that this fragment, which once possessed a powerful destructive force, could finally be found and brought back, like other found fragments, has nothing to do with longing.

Most of the time, the process of finding an anomaly is more like chasing the footprints of the wind; it comes without a shadow and goes without a trace, without logic, and without need for reason.

This old, incomplete shell, containing sorrow and pain... That it could be found is hardly a miracle, but simply because those who wished to find it all held the purest of emotions in their hearts, that is all. And this existence that connects things has now finally reached her lips.

Description

Vance and Drem tell Caimeng that the $\text{mex}$ of a sequence of non-negative integers is the smallest non-negative integer that does not appear in it; for example, $\text{mex}([0,1,3])=2$.

Caimeng defines the $\text{xormex}$ of a sequence of non-negative integers as the maximum $\text{mex}$ of the sequence after XORing each element with the same non-negative integer; for example, $\text{xormex}([8,9,11])=\text{mex}([8\oplus 9,9\oplus 9,11\oplus 9])=\text{mex}([1,0,2])=3$.

Given a sequence $a$ of length $2^n$ and $m$ queries, each query provides two integers $l, r$. Caimeng wants to know the answers to the following two questions:

• The $\text{xormex}$ of the subsegment $[a_l, a_{l+1}, \dots, a_r]$.
• The sum of the $\text{xormex}$ of all subsegments $[a_x, a_{x+1}, \dots, a_y]$ where $l \leq x \leq y \leq r$.

Input

The first line contains three integers $n, m, o$.

The second line contains $2^n$ integers $a_i$.

The next $m$ lines each contain two integers $l, r$.

Output

Output $m$ lines, each containing an integer representing the answer to each query.

If $o=1$, you need to output the answer to the first question.

If $o=2$, you need to output the answer to the second question.

Examples

Input 1

2 4 1
3 2 0 1
1 3
2 3
1 2
1 4

Output 1

3
1
2
4

Input 2

3 5 2
0 4 6 7 5 2 1 3
1 8
3 5
2 6
3 7
1 4

Output 2

93
9
29
22
15

Note

For the first query, $\text{xormex}([3,2,0])=\text{mex}([3\oplus 2,2\oplus 2,0\oplus 2])=\text{mex}([1,0,2])=3$.

For the second query, $\text{xormex}([2,0])=\text{mex}([2,0])=1$.

For the third query, $\text{xormex}([3,2])=\text{mex}([3\oplus 3,2\oplus 3])=\text{mex}([0,1])=2$.

For the fourth query, $\text{xormex}([3,2,0,1])=\text{mex}([3,2,0,1])=4$.

Constraints

For all data, $1\le n\le 18$, $1\le m\le 10^6$, $0\le a_i < 2^n$, $1\le l\le r\le 2^n$.

There are 37 test cases in total. There are dependencies between subtasks; please do not submit frequently.

Postscript

What pulled her back from the boundary of life and death... was it a good prescription, or a miracle? Or perhaps friendship?

...Perhaps, it was all of them.

When her dreams were first lit up by light, she saw her friends throwing themselves into danger to protect her. She was certain that she would do the same when they encountered danger. She would definitely protect them well—including, of course, the new friend she had just met.

When they were finally able to let go of their burdens, to calmly share the paths they had walked, and to tell of the kindness they had encountered from strangers...

Caimeng couldn't help but smile, her mouth curving into a beautiful arc. To be able to smile freely and at peace, how incredibly lucky that is.