Институт по изучению дронов в естественных условиях при правительстве Галактической Федерации занимается изучением дронов в естественных условиях. В настоящий момент институт проводит исследования по влиянию на дронов различной музыки. Пока ученым удалось установить, что если транслировать дронам в естественных условиях звуковые волны определенной частоты, то в зависимости от возраста некоторые дроны засыпают, другие — перегорают, а остальные ведут себя естественно.
Предположим, возраст некоторого дрона равен A и ему транслируется звуковая волна частотой B. Тогда, судя по экспериментальным данным, если , то дрон засыпает, а если , то перегорает. Если ни одно из условий не выполняется, дрон ведет себя естественно.
— это операция побитового сложения по модулю два, также известная как XOR и побитовое исключающее «ИЛИ». Результатом такой операции будет число, каждый бит которого зависит от значений битов в соответствующих разрядах двоичной записи операндов. Если биты в разряде k операндов равны, то в разряде k результата будет стоять 0, в противном случае — 1.
Чтобы не выводить лишний раз дронов из спячки и не менять предохранители, ученые хотят теоретически определить, сколько дронов при воздействии той или иной звуковой волны заснут, а сколько перегорят.
В первой строке задано количество дронов N (1 ≤ N ≤ 105).
Следующая строка содержит N целых чисел Ai (1 ≤ Ai ≤ 109) — возраста дронов, участвующих в экспериментах. По ходу моделирования всех экспериментов можно считать, что возраста дронов не меняются.
В следующей строке задано количество экспериментов, которые необходимо промоделировать Q (1 ≤ Q ≤ 105).
Последняя строка содержит Q целых чисел Bj (1 ≤ Bj ≤ 109) — частоты звуковых волн, транслируемые в разных экспериментах.
Выведите Q строк — результатов экспериментов.
Каждый результат должен содержать два числа — количество заснувших и количество перегоревших дронов в соответствующем эксперименте.
В первом эксперименте перегорают дроны 1, 2 и 3. Во втором и третьем засыпает дрон 3. В четвертом и пятом засыпает дрон 1, а перегорают дроны 2 и 3. В шестом и седьмом засыпает дрон 1, а перегорает 2. В последнем эксперименте засыпает дрон 2, а перегорают дроны 1 и 3.
## Входные Данные
В первой строке задано количество дронов N (1 ≤ N ≤ 105).Следующая строка содержит N целых чисел Ai (1 ≤ Ai ≤ 109) — возраста дронов, участвующих в экспериментах. По ходу моделирования всех экспериментов можно считать, что возраста дронов не меняются.В следующей строке задано количество экспериментов, которые необходимо промоделировать Q (1 ≤ Q ≤ 105).Последняя строка содержит Q целых чисел Bj (1 ≤ Bj ≤ 109) — частоты звуковых волн, транслируемые в разных экспериментах.
## Выходные Данные
Выведите Q строк — результатов экспериментов.Каждый результат должен содержать два числа — количество заснувших и количество перегоревших дронов в соответствующем эксперименте.
## Пример
Входные данные36 10 281 2 3 4 5 6 7 8Выходные данные0 31 01 01 21 21 11 11 2
## Примечание
В первом эксперименте перегорают дроны 1, 2 и 3. Во втором и третьем засыпает дрон 3. В четвертом и пятом засыпает дрон 1, а перегорают дроны 2 и 3. В шестом и седьмом засыпает дрон 1, а перегорает 2. В последнем эксперименте засыпает дрон 2, а перегорают дроны 1 и 3.
[samples]
**Definitions**
Let $ N \in \mathbb{Z}^+ $ be the number of drones.
Let $ A = (a_1, a_2, \dots, a_N) $ be the sequence of drone ages, where $ a_i \in \mathbb{Z} $, $ 1 \le a_i \le 10^9 $.
Let $ Q \in \mathbb{Z}^+ $ be the number of experiments.
Let $ B = (b_1, b_2, \dots, b_Q) $ be the sequence of sound frequencies, where $ b_j \in \mathbb{Z} $, $ 1 \le b_j \le 10^9 $.
**Constraints**
1. $ 1 \le N \le 10^5 $
2. $ 1 \le Q \le 10^5 $
3. $ 1 \le a_i \le 10^9 $ for all $ i \in \{1, \dots, N\} $
4. $ 1 \le b_j \le 10^9 $ for all $ j \in \{1, \dots, Q\} $
**Objective**
For each experiment $ j \in \{1, \dots, Q\} $, with frequency $ b_j $, compute:
- $ s_j = \left| \left\{ i \in \{1, \dots, N\} \mid a_i \oplus b_j < a_i \right\} \right| $: number of drones that fall asleep,
- $ d_j = \left| \left\{ i \in \{1, \dots, N\} \mid a_i \oplus b_j > a_i \right\} \right| $: number of drones that burn out.
Output $ (s_j, d_j) $ for each $ j \in \{1, \dots, Q\} $.