{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eAlice has a very important message \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/span\u003e 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 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eK\u003c/i\u003e\u003c/span\u003e of the length equal to the message\u0027s length. Alice computes the bitwise xor of each element of the message and the key (\u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/83287e0fe0cb440b6da6473e1f5a2a4b?v\u003d1725702470\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e, where \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/f2fe3e60ef565744bf61ec18d7bc2fbe?v\u003d1725702470\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e denotes the \u003ca href\u003d\"https://en.wikipedia.org/wiki/Bitwise_operation#XOR\"\u003ebitwise XOR operation\u003c/a\u003e) and stores this encrypted message \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003c/span\u003e. Alice is smart. Be like Alice.\u003c/p\u003e\u003cp\u003eFor example, Alice may have wanted to store a message \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eM\u003c/i\u003e \u003d (0, 15, 9, 18)\u003c/span\u003e. She generated a key \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eK\u003c/i\u003e \u003d (16, 7, 6, 3)\u003c/span\u003e. The encrypted message is thus \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e \u003d (16, 8, 15, 17)\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eAlice realised that she cannot store the key with the encrypted message. Alice sent her key \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eK\u003c/i\u003e\u003c/span\u003e to Bob and deleted her own copy. Alice is smart. Really, be like Alice.\u003c/p\u003e\u003cp\u003eBob 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\u0027t be like Bob.\u003c/p\u003e\u003cp\u003eIn the above example, Bob may have, for instance, selected a permutation \u003cspan class\u003d\"tex-span\"\u003e(3, 4, 1, 2)\u003c/span\u003e and stored the permuted key \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eP\u003c/i\u003e \u003d (6, 3, 16, 7)\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eOne 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\u0027t smart?\u003c/p\u003e\u003cp\u003eBob 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 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003c/span\u003e and the permuted key \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eP\u003c/i\u003e\u003c/span\u003e. What is the lexicographically smallest message that could have resulted in the given encrypted text?\u003c/p\u003e\u003cp\u003eMore precisely, for given \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eP\u003c/i\u003e\u003c/span\u003e, find the lexicographically smallest message \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eO\u003c/i\u003e\u003c/span\u003e, for which there exists a permutation \u003cspan class\u003d\"tex-span\"\u003eπ\u003c/span\u003e such that \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/37d629bea8d619f33858afd9e045f06c?v\u003d1725702470\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e for every \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eNote that the sequence \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eS\u003c/i\u003e\u003c/span\u003e is lexicographically smaller than the sequence \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/span\u003e, if there is an index \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e such that \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eS\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e \u0026lt; \u003ci\u003eT\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e and for all \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e \u0026lt; \u003ci\u003ei\u003c/i\u003e\u003c/span\u003e the condition \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eS\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e \u003d \u003ci\u003eT\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e holds. \u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains a single integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 300000\u003c/span\u003e), the length of the message. \u003c/p\u003e\u003cp\u003eThe second line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003eA\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003eA\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e0 ≤ \u003ci\u003eA\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e \u0026lt; 2\u003csup class\u003d\"upper-index\"\u003e30\u003c/sup\u003e\u003c/span\u003e) representing the encrypted message.\u003c/p\u003e\u003cp\u003eThe third line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eP\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003eP\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003eP\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e0 ≤ \u003ci\u003eP\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e \u0026lt; 2\u003csup class\u003d\"upper-index\"\u003e30\u003c/sup\u003e\u003c/span\u003e) representing the permuted encryption key.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput a single line with \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e integers, the lexicographically smallest possible message \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eO\u003c/i\u003e\u003c/span\u003e. Note that all its elements should be non-negative.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n8 4 13\n17 2 7\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10 3 28\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\n12 7 87 22 11\n18 39 9 12 16\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0 14 69 6 44\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e10\n331415699 278745619 998190004 423175621 42983144 166555524 843586353 802130100 337889448 685310951\n226011312 266003835 342809544 504667531 529814910 684873393 817026985 844010788 993949858 1031395667\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e128965467 243912600 4281110 112029883 223689619 76924724 429589 119397893 613490433 362863284\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first case, the solution is \u003cspan class\u003d\"tex-span\"\u003e(10, 3, 28)\u003c/span\u003e, since \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/07030798389b4101f147e25639e5fc13?v\u003d1725702470\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e, \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/8e030c9c3eef72b401114572214facb9?v\u003d1725702470\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e and \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/9c4fc40f12f1540ef407464111ac6793?v\u003d1725702470\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e. Other possible permutations of key yield messages \u003cspan class\u003d\"tex-span\"\u003e(25, 6, 10)\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e(25, 3, 15)\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e(10, 21, 10)\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e(15, 21, 15)\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e(15, 6, 28)\u003c/span\u003e, which are all lexicographically larger than the solution.\u003c/p\u003e"}}]}