C. Perfect Security

Codeforces

IDCF947C

Time3000ms

Memory512MB

Difficulty—

data structuresgreedystringstrees

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. For 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). Alice 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. Bob 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. In 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). One 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? Bob 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? More precisely, for given _A_ and _P_, find the lexicographically smallest message _O_, for which there exists a permutation π such that for every _i_. Note 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. ## Input The first line contains a single integer _N_ (1 ≤ _N_ ≤ 300000), the length of the message. The second line contains _N_ integers _A_1, _A_2, ..., _A__N_ (0 ≤ _A__i_ < 230) representing the encrypted message. The third line contains _N_ integers _P_1, _P_2, ..., _P__N_ (0 ≤ _P__i_ < 230) representing the permuted encryption key. ## Output Output a single line with _N_ integers, the lexicographically smallest possible message _O_. Note that all its elements should be non-negative. [samples] ## Note 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.

Samples

Input #1

3
8 4 13
17 2 7

Output #1

10 3 28

Input #2

5
12 7 87 22 11
18 39 9 12 16

Output #2

0 14 69 6 44

Input #3

10
331415699 278745619 998190004 423175621 42983144 166555524 843586353 802130100 337889448 685310951
226011312 266003835 342809544 504667531 529814910 684873393 817026985 844010788 993949858 1031395667

Output #3

128965467 243912600 4281110 112029883 223689619 76924724 429589 119397893 613490433 362863284

API Response (JSON)

{
  "problem": {
    "name": "C. Perfect Security",
    "description": {
      "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 gen",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF947C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "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 gen...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments