Queries on array

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

You are given an array \(a\) of \(n\) integers.

An array element \(a_i\) is a local maximum if \(2 \le i \le n - 1\) and \(a_{i-1} < a_i > a_{i+1}\).

You need to answer \(q\) queries.

A query is given by an integer \(x\). For the query, you must perform the operation \(a_i := a_i \mbox{ XOR } x\) for each element of the array. After that, you need to output the number of local maxima in the array.

Note that the queries modify the array and are dependent on each other — the next query is executed after the previous ones.

Input

The first line contains an integer \(n\) — the length of the array.

The second line contains \(n\) integers \(a_i\) — the elements of the array.

The third line contains an integer \(q\) — the number of queries.

The next \(q\) lines each contain a single integer \(x\).

Output

Output \(q\) lines. In the \(i\)-th line, output an integer — the answer to the \(i\)-th query.

Constraints

\(1 \le n \le 10^5\),

\(1 \le a_i \le 10^9\),

\(1 \le q \le 10^5\),

\(0 \le x \le 10^9\).

Samples

Input (stdin) сopy	Output (stdout) сopy
7 1 3 1 5 9 7 11 5 10 3 4 7 11	2 3 2 2 2