Запити на масиві

Limits: 2 sec., 256 MiB

Задано масив $a$ з $n$ цілих чисел.

Елемент масиву $a_i$ є локальним максимумом, якщо $2 \le i \le n - 1$ і $a_{i-1} < a_i > a_{i+1}$.

Вам потрібно відповісти на $q$ запитів.

Запит задається цілим числом $x$. Для запиту ви повинні зробити операцію $a_i := a_i \mbox{ XOR } x$ для кожного елемента масиву. Після цього треба сказати кількість локальних максимумів у масиві.

Зауважте, що запити змінюють масив і є залежними між собою — наступний запит виконується після попередніх.

Input

У першому рядку задано ціле число $n$ — довжину масиву.

У другому рядку задано $n$ цілих чисел $a_i$ — елементи масиву.

У третьому рядку задано ціле число $q$ — кількість запитів.

Наступні $q$ рядків містять по одному цілому числу $x$.

Output

Виведіть $q$ рядків. В $i$-ому рядку виведіть ціле число — відповідь на $i$-ий запит.

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