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

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