शर्बत और गेलतो ने संदेश को एन्क्रिप्ट किया
Problem
शर्बत और गेलतो ने महत्वपूर्ण डेटा सीखा। यह डेटा एक रहस्य है जिसका खुलासा नहीं किया जा सकता है, लेकिन उनकी मात्रा इतनी बड़ी थी कि उन्हें पूरी तरह याद रखना संभव नहीं था। इसलिए उन्होंने उन्हें एन्क्रिप्ट करने का फैसला किया।
सॉर्बेट ने डेटा से एक संदेश संकलित किया। डिजिटलीकरण के बाद, संदेश n गैर-ऋणात्मक पूर्णांकों का अनुक्रम M था। एन्क्रिप्शन के लिए, सॉर्बेट ने एक यादृच्छिक कुंजी K उत्पन्न की, जो n गैर-ऋणात्मक पूर्णांकों का एक अनुक्रम भी था।
उसके बाद, इसने एन्क्रिप्टेड संदेश A को मूल संदेश के प्रत्येक संबंधित तत्व के बिटवाइज़ XOR के रूप में और कुंजी (Ai = Mi ⊕ K की गणना की। मैं) .
सॉर्बेट ने एन्क्रिप्टेड संदेश अपने लिए रखा, और सुरक्षा सुनिश्चित करने के लिए, कुंजी को जिलेटो को भेजा गया, और उसने इसे मिटा दिया। हालांकि, ट्रांसमिशन चैनल अविश्वसनीय साबित हुआ और जिलेटो ने कुंजी पी प्राप्त की, जिसमें के से कुछ तत्वों की अदला-बदली की गई। यानी, मुझे मूल कुंजी K का कुछ क्रमचय मिला।
जब संदेश को वापस डिकोड करने का समय आया, तो समस्या का एहसास होने पर वे भयभीत हो गए। हालाँकि, सॉर्बेट को याद था कि मूल संदेश शब्दावली की दृष्टि से काफी छोटा था (लेकिन इसमें केवल गैर-नकारात्मक संख्याएँ थीं)।
तो सॉर्बेट और गेलैटो ने यह पता लगाने का फैसला किया कि लेक्सिकोग्राफिक रूप से सबसे छोटा संदेश क्या है जिसे एन्क्रिप्ट किया जा सकता है। इसका पता लगाने में उनकी मदद करें।
इनपुट:
पहली पंक्ति में एक पूर्णांक n (1 ≤ n ≤ 300000) — संदेश की लंबाई।
दूसरी पंक्ति में n पूर्णांक A1, A2, ..., An (0 ≤ ऐ < 230) — एन्क्रिप्टेड संदेश।
तीसरी पंक्ति में n पूर्णांक P1, P2, ..., Pn (0 ≤ पाई < 230) — एक एन्क्रिप्शन कुंजी जिसके तत्वों को मनमाने ढंग से पुनर्व्यवस्थित किया जाता है।
आउटपुट:
n पूर्णांकों वाली एक पंक्ति प्रिंट करें — शाब्दिक रूप से सबसे छोटा संभव मूल संदेश। याद रखें कि इसमें सभी संख्याएँ गैर-ऋणात्मक होनी चाहिए।
उदाहरण:
<तालिका सीमा = "1" सेलपैडिंग = "1" सेलस्पेसिंग = "1" शैली = "चौड़ाई: 500 पीएक्स;">
<शरीर>
| इनपुट |
आउटपुट |
3
8 4 13
17 2 7
| 10 3 28 |
5
12 7 87 22 11
18 39 9 12 16
| 0 14 69 6 44 |
व्याख्या:
पहले उदाहरण में, समाधान है (10, 3, 28) क्योंकि 8 ⊕ 2 = 10, 4 + 7 = 3 और 13 + 17 = 28.
अन्य संभावित कुंजी क्रमपरिवर्तन संदेश देते हैं (25, 6, 10), (25, 3, 15), (10, 21, 10), (15, 21, 15) और (15, 6, 28), जिनमें से सभी लेक्सिकोग्राफिक रूप से इष्टतम समाधान से बड़े हैं।