{"problem":{"name":"J. Дроны","description":{"content":"Институт по изучению дронов в естественных условиях при правительстве Галактической Федерации занимается изучением дронов в естественных условиях. В настоящий момент институт проводит исследования по ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10136J"},"statements":[{"statement_type":"Markdown","content":"Институт по изучению дронов в естественных условиях при правительстве Галактической Федерации занимается изучением дронов в естественных условиях. В настоящий момент институт проводит исследования по влиянию на дронов различной музыки. Пока ученым удалось установить, что если транслировать дронам в естественных условиях звуковые волны определенной частоты, то в зависимости от возраста некоторые дроны засыпают, другие — перегорают, а остальные ведут себя естественно.\n\nПредположим, возраст некоторого дрона равен A и ему транслируется звуковая волна частотой B. Тогда, судя по экспериментальным данным, если , то дрон засыпает, а если , то перегорает. Если ни одно из условий не выполняется, дрон ведет себя естественно. \n\n — это операция побитового сложения по модулю два, также известная как XOR и побитовое исключающее «ИЛИ». Результатом такой операции будет число, каждый бит которого зависит от значений битов в соответствующих разрядах двоичной записи операндов. Если биты в разряде k операндов равны, то в разряде k результата будет стоять 0, в противном случае — 1.\n\nЧтобы не выводить лишний раз дронов из спячки и не менять предохранители, ученые хотят теоретически определить, сколько дронов при воздействии той или иной звуковой волны заснут, а сколько перегорят.\n\nВ первой строке задано количество дронов N (1 ≤ N ≤ 105).\n\nСледующая строка содержит N целых чисел Ai (1 ≤ Ai ≤ 109) — возраста дронов, участвующих в экспериментах. По ходу моделирования всех экспериментов можно считать, что возраста дронов не меняются.\n\nВ следующей строке задано количество экспериментов, которые необходимо промоделировать Q (1 ≤ Q ≤ 105).\n\nПоследняя строка содержит Q целых чисел Bj (1 ≤ Bj ≤ 109) — частоты звуковых волн, транслируемые в разных экспериментах.\n\nВыведите Q строк — результатов экспериментов.\n\nКаждый результат должен содержать два числа — количество заснувших и количество перегоревших дронов в соответствующем эксперименте.\n\nВ первом эксперименте перегорают дроны 1, 2 и 3. Во втором и третьем засыпает дрон 3. В четвертом и пятом засыпает дрон 1, а перегорают дроны 2 и 3. В шестом и седьмом засыпает дрон 1, а перегорает 2. В последнем эксперименте засыпает дрон 2, а перегорают дроны 1 и 3.\n\n## Входные Данные\n\nВ первой строке задано количество дронов N (1 ≤ N ≤ 105).Следующая строка содержит N целых чисел Ai (1 ≤ Ai ≤ 109) — возраста дронов, участвующих в экспериментах. По ходу моделирования всех экспериментов можно считать, что возраста дронов не меняются.В следующей строке задано количество экспериментов, которые необходимо промоделировать Q (1 ≤ Q ≤ 105).Последняя строка содержит Q целых чисел Bj (1 ≤ Bj ≤ 109) — частоты звуковых волн, транслируемые в разных экспериментах.\n\n## Выходные Данные\n\nВыведите Q строк — результатов экспериментов.Каждый результат должен содержать два числа — количество заснувших и количество перегоревших дронов в соответствующем эксперименте.\n\n## Пример\n\nВходные данные36 10 281 2 3 4 5 6 7 8Выходные данные0 31 01 01 21 21 11 11 2\n\n## Примечание\n\nВ первом эксперименте перегорают дроны 1, 2 и 3. Во втором и третьем засыпает дрон 3. В четвертом и пятом засыпает дрон 1, а перегорают дроны 2 и 3. В шестом и седьмом засыпает дрон 1, а перегорает 2. В последнем эксперименте засыпает дрон 2, а перегорают дроны 1 и 3.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of drones.  \nLet $ 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 $.  \nLet $ Q \\in \\mathbb{Z}^+ $ be the number of experiments.  \nLet $ 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 $.  \n\n**Constraints**  \n1. $ 1 \\le N \\le 10^5 $  \n2. $ 1 \\le Q \\le 10^5 $  \n3. $ 1 \\le a_i \\le 10^9 $ for all $ i \\in \\{1, \\dots, N\\} $  \n4. $ 1 \\le b_j \\le 10^9 $ for all $ j \\in \\{1, \\dots, Q\\} $  \n\n**Objective**  \nFor each experiment $ j \\in \\{1, \\dots, Q\\} $, with frequency $ b_j $, compute:  \n- $ 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,  \n- $ 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.  \n\nOutput $ (s_j, d_j) $ for each $ j \\in \\{1, \\dots, Q\\} $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10136J","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}