{"raw_statement":[{"iden":"statement","content":"Alice has a very important message _M_ consisting of some non-negative integers that she wants to keep secret from Eve. Alice knows that the only theoretically secure cipher is one-time pad. Alice generates a random key _K_ of the length equal to the message's length. Alice computes the bitwise xor of each element of the message and the key (, where denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)) and stores this encrypted message _A_. Alice is smart. Be like Alice.\n\nFor example, Alice may have wanted to store a message _M_ = (0, 15, 9, 18). She generated a key _K_ = (16, 7, 6, 3). The encrypted message is thus _A_ = (16, 8, 15, 17).\n\nAlice realised that she cannot store the key with the encrypted message. Alice sent her key _K_ to Bob and deleted her own copy. Alice is smart. Really, be like Alice.\n\nBob realised that the encrypted message is only secure as long as the key is secret. Bob thus randomly permuted the key before storing it. Bob thinks that this way, even if Eve gets both the encrypted message and the key, she will not be able to read the message. Bob is not smart. Don't be like Bob.\n\nIn the above example, Bob may have, for instance, selected a permutation (3, 4, 1, 2) and stored the permuted key _P_ = (6, 3, 16, 7).\n\nOne year has passed and Alice wants to decrypt her message. Only now Bob has realised that this is impossible. As he has permuted the key randomly, the message is lost forever. Did we mention that Bob isn't smart?\n\nBob wants to salvage at least some information from the message. Since he is not so smart, he asks for your help. You know the encrypted message _A_ and the permuted key _P_. What is the lexicographically smallest message that could have resulted in the given encrypted text?\n\nMore precisely, for given _A_ and _P_, find the lexicographically smallest message _O_, for which there exists a permutation π such that for every _i_.\n\nNote that the sequence _S_ is lexicographically smaller than the sequence _T_, if there is an index _i_ such that _S__i_ < _T__i_ and for all _j_ < _i_ the condition _S__j_ = _T__j_ holds."},{"iden":"input","content":"The first line contains a single integer _N_ (1 ≤ _N_ ≤ 300000), the length of the message.\n\nThe second line contains _N_ integers _A_1, _A_2, ..., _A__N_ (0 ≤ _A__i_ < 230) representing the encrypted message.\n\nThe third line contains _N_ integers _P_1, _P_2, ..., _P__N_ (0 ≤ _P__i_ < 230) representing the permuted encryption key."},{"iden":"output","content":"Output a single line with _N_ integers, the lexicographically smallest possible message _O_. Note that all its elements should be non-negative."},{"iden":"examples","content":"Input\n\n3\n8 4 13\n17 2 7\n\nOutput\n\n10 3 28\n\nInput\n\n5\n12 7 87 22 11\n18 39 9 12 16\n\nOutput\n\n0 14 69 6 44\n\nInput\n\n10\n331415699 278745619 998190004 423175621 42983144 166555524 843586353 802130100 337889448 685310951\n226011312 266003835 342809544 504667531 529814910 684873393 817026985 844010788 993949858 1031395667\n\nOutput\n\n128965467 243912600 4281110 112029883 223689619 76924724 429589 119397893 613490433 362863284"},{"iden":"note","content":"In the first case, the solution is (10, 3, 28), since , and . Other possible permutations of key yield messages (25, 6, 10), (25, 3, 15), (10, 21, 10), (15, 21, 15) and (15, 6, 28), which are all lexicographically larger than the solution."}],"translated_statement":[{"iden":"statement","content":"Alice 有一个非常重要的消息 #cf_span[M]，由一些非负整数组成，她希望对 Eve 保密。Alice 知道唯一理论上安全的加密方法是一次一密。Alice 生成了一个与消息长度相等的随机密钥 #cf_span[K]。Alice 对消息的每个元素与密钥进行按位异或运算（即 ，其中  表示按位异或操作），并将加密后的消息存储为 #cf_span[A]。Alice 很聪明。请像 Alice 一样。\n\n例如，Alice 可能想存储消息 #cf_span[M = (0, 15, 9, 18)]。她生成了密钥 #cf_span[K = (16, 7, 6, 3)]。因此，加密后的消息是 #cf_span[A = (16, 8, 15, 17)]。\n\nAlice 意识到她不能将密钥与加密消息一起存储。于是她将密钥 #cf_span[K] 发送给 Bob，并删除了自己手中的副本。Alice 很聪明。真的，请像 Alice 一样。\n\nBob 意识到，只要密钥保密，加密消息就是安全的。因此，Bob 在存储前随机打乱了密钥。Bob 认为，即使 Eve 同时获得了加密消息和密钥，她也无法读取消息。Bob 不聪明。请不要像 Bob 一样。\n\n在上述例子中，Bob 可能选择了排列 #cf_span[(3, 4, 1, 2)]，并将打乱后的密钥存储为 #cf_span[P = (6, 3, 16, 7)]。\n\n一年过去了，Alice 想要解密她的消息。此时 Bob 才意识到这是不可能的。由于他随机打乱了密钥，消息已永远丢失。我们提到过 Bob 不聪明吗？\n\nBob 希望至少能从消息中挽救一些信息。由于他不够聪明，他向你求助。你知道加密消息 #cf_span[A] 和打乱后的密钥 #cf_span[P]。请问，可能产生该加密文本的字典序最小的消息是什么？\n\n更准确地说，对于给定的 #cf_span[A] 和 #cf_span[P]，找出字典序最小的消息 #cf_span[O]，使得存在一个排列 #cf_span[π]，满足对所有 #cf_span[i] 有 。\n\n注意，序列 #cf_span[S] 字典序小于序列 #cf_span[T]，当且仅当存在一个下标 #cf_span[i]，使得 #cf_span[Si < Ti]，且对所有 #cf_span[j < i] 都有 #cf_span[Sj = Tj]。\n\n第一行包含一个整数 #cf_span[N]（#cf_span[1 ≤ N ≤ 300000]），表示消息的长度。\n\n第二行包含 #cf_span[N] 个整数 #cf_span[A1, A2, ..., AN]（#cf_span[0 ≤ Ai < 230]），表示加密消息。\n\n第三行包含 #cf_span[N] 个整数 #cf_span[P1, P2, ..., PN]（#cf_span[0 ≤ Pi < 230]），表示打乱后的加密密钥。\n\n请输出一行 #cf_span[N] 个整数，表示字典序最小的可能消息 #cf_span[O]。注意，所有元素必须为非负整数。\n\n在第一组样例中，解为 #cf_span[(10, 3, 28)]，因为 ， 且 。其他可能的密钥排列产生的消息为 #cf_span[(25, 6, 10)]、#cf_span[(25, 3, 15)]、#cf_span[(10, 21, 10)]、#cf_span[(15, 21, 15)] 和 #cf_span[(15, 6, 28)]，它们的字典序均大于该解。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[N]（#cf_span[1 ≤ N ≤ 300000]），表示消息的长度。第二行包含 #cf_span[N] 个整数 #cf_span[A1, A2, ..., AN]（#cf_span[0 ≤ Ai < 230]），表示加密消息。第三行包含 #cf_span[N] 个整数 #cf_span[P1, P2, ..., PN]（#cf_span[0 ≤ Pi < 230]），表示打乱后的加密密钥。"},{"iden":"output","content":"请输出一行 #cf_span[N] 个整数，表示字典序最小的可能消息 #cf_span[O]。注意，所有元素必须为非负整数。"},{"iden":"examples","content":"输入38 4 1317 2 7输出10 3 28输入512 7 87 22 1118 39 9 12 16输出0 14 69 6 44输入10331415699 278745619 998190004 423175621 42983144 166555524 843586353 802130100 337889448 685310951226011312 266003835 342809544 504667531 529814910 684873393 817026985 844010788 993949858 1031395667输出128965467 243912600 4281110 112029883 223689619 76924724 429589 119397893 613490433 362863284"},{"iden":"note","content":"在第一组样例中，解为 #cf_span[(10, 3, 28)]，因为 ， 且 。其他可能的密钥排列产生的消息为 #cf_span[(25, 6, 10)]、#cf_span[(25, 3, 15)]、#cf_span[(10, 21, 10)]、#cf_span[(15, 21, 15)] 和 #cf_span[(15, 6, 28)]，它们的字典序均大于该解。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the message.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be the encrypted message, where $ a_i \\in \\mathbb{Z} $, $ 0 \\le a_i < 2^{30} $.  \nLet $ P = (p_1, p_2, \\dots, p_n) $ be the permuted key, where $ p_i \\in \\mathbb{Z} $, $ 0 \\le p_i < 2^{30} $.  \n\n**Constraints**  \n1. $ 1 \\le n \\le 300000 $  \n2. $ 0 \\le a_i < 2^{30} $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. $ 0 \\le p_i < 2^{30} $ for all $ i \\in \\{1, \\dots, n\\} $  \n\n**Objective**  \nFind the lexicographically smallest sequence $ O = (o_1, o_2, \\dots, o_n) $, where $ o_i \\in \\mathbb{Z}_{\\ge 0} $, such that there exists a permutation $ \\pi \\in S_n $ satisfying:  \n$$\no_i = a_i \\oplus p_{\\pi(i)} \\quad \\text{for all } i \\in \\{1, \\dots, n\\}\n$$  \nand $ \\pi $ is a bijection from $ \\{1, \\dots, n\\} $ to $ \\{1, \\dots, n\\} $.","simple_statement":null,"has_page_source":false}