Problem Statement

We have $N$ gemstones. The color and beauty of the $i$-th gemstone are $D_i$ and $V_i$, respectively. Here, the color of each gemstone is one of $1, 2, \ldots, C$, and there is at least one gemstone of each color.

Out of the $N$ gemstones, we will choose $C$ with distinct colors and use them to make a necklace. (The order does not matter.) The beautifulness of the necklace will be the bitwise $\rm XOR$ of the chosen gemstones.

Among all possible ways to make a necklace, find the beautifulness of the necklace made in the way with the $K$-th greatest beautifulness. (If there are multiple ways with the same beautifulness, we count all of them.)

What is bitwise $\rm XOR$? The bitwise $\rm XOR$ of integers $A$ and $B$, $A \oplus B$, is defined as follows: When $A \oplus B$ is written in base two, the digit in the $2^k$'s place ($k \geq 0$) is $1$ if either $A$ or $B$, but not both, has $1$ in the $2^k$'s place, and $0$ otherwise. For example, $3 \oplus 5 = 6$. (In base two: $011 \oplus 101 = 110$.)

Constraints

• $1 \leq C \leq N \leq 70$
• $1 \leq D_i \leq C$
• $0 \leq V_i < 2^{60}$
• $1 \leq K \leq 10^{18}$
• There are at least $K$ ways to make a necklace.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N C K
D_1 V_1
\vdots
D_N V_N

Output

Print the answer.