2. Reorder it

Problem Statement

2. Reorder it You are given two integer arrays A and B , both of length N , and an integer P used for hashing. The array C , also of length N , is defined by C[i] = (A[i] + B[i]) % N Before C is built you may permute the elements of exactly one of the two arrays — either A or B , but never both. The other array keeps its given order. Choose the permutation (and which array to permute) so that the resulting C is lexicographically smallest , then report the hash of that C . With C 0-indexed, the hash is hash = ( sum over i of C[i] * P^i ) % (10^9 + 7) , for i from 0 to N-1 . Doing nothing is allowed: the identity permutation is a legal choice, so the original order is always among the candidates. Input Format The first line contains the integer N , the length of both arrays. The second line contains the integer P , the base of the hash. Each of the next N lines contains one integer: line i holds A[i] . Each of the next N lines contains one integer: line i holds B[i] . Output Format Print