JSOI is a kingdom with a long history. Recently, archaeologists discovered an ancient prophecy in a tomb. Although the conclusion part is incomplete, the derivation process remains intact. The prophecy concerns the date of the world's destruction, and King JS has entrusted the important task of deciphering the prophecy to the Minister of Culture, JYY.

The prophecy consists of three parts: Heaven, Earth, and Man:

The first part, "Heaven," comes from the revelations of the gods to the ancient JSOI prophets. It consists of $N$ elements, represented by 32-bit unsigned integers, denoted as $a_1$ to $a_n$.

The second part, "Earth," comes from the observations of the world by the ancient JSOI people. It consists of $N$ elements, represented by 32-bit unsigned integers, denoted as $b_1$ to $b_n$.

The third part, "Man," comes from the JSOI people's belief regarding the date the world will be destroyed, represented by a 64-bit unsigned integer, denoted as $t$.

The derivation process for the prophecy $f$ is as follows:

$$f(x) = \begin{cases} a_x, & x \le N \\ \bigoplus_{i=1}^{n} (f(x-i) \land b_i), & x > N \end{cases}$$

Where $\land$ denotes the bitwise AND operation, and $\bigoplus$ denotes the bitwise XOR operation. Now, JYY wants to find the value of $f(t)$.

Input

The first line contains a positive integer $N$. The second line contains $N$ unsigned integers $a_i$. The third line contains $N$ unsigned integers $b_i$. The fourth line contains an integer $t$.

Output

Output a single integer, the value of $f(t)$.

Constraints

• For 10% of the data, $t \le 1000$;
• For another 20% of the data, $N \le 100$;
• For 100% of the data, $1 \le N \le 1000$, $t \le 10^{18}$.

Examples

Input 1

3
10 20 30
7 19 13
5

Output 1

16

Input 2

5
2345678901 1001001001 3333333333 3141592653 1234567890
2147483648 2147483647 4294967295 4294967294 3434343434
100

Output 2

1067078691