Algorithm

E. Minimum Array
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two arrays a and b, both of length n. All elements of both arrays are from 00 to n1�−1.

You can reorder elements of the array b (if you want, you may leave the order of elements as it is). After that, let array c be the array of length n, the i-th element of this array is ci=(ai+bi)%n��=(��+��)%�, where x%y�%� is x modulo y.

Your task is to reorder elements of the array b to obtain the lexicographically minimum possible array c.

Array x of length n is lexicographically less than array y of length n, if there exists such i (1in1≤�≤�), that xi<yi��<��, and for any j (1j<i1≤�<�xj=yj��=��.

Input

The first line of the input contains one integer n (1n21051≤�≤2⋅105) — the number of elements in ab and c.

The second line of the input contains n integers a1,a2,,an�1,�2,…,�� (0ai<n0≤��<�), where ai�� is the i-th element of a.

The third line of the input contains n integers b1,b2,,bn�1,�2,…,�� (0bi<n0≤��<�), where bi�� is the i-th element of b.

Output

Print the lexicographically minimum possible array c. Recall that your task is to reorder elements of the array b and obtain the lexicographically minimum possible array c, where the i-th element of c is ci=(ai+bi)%n��=(��+��)%�.

Examples
input
Copy
4
0 1 2 1
3 2 1 1

output
Copy
1 0 0 2

input
Copy
7
2 5 1 5 3 4 3
2 4 3 5 6 5 1

output
Copy
0 0 0 1 0 2 4

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int const N = 2e5 + 1;
int n, a[N], b[N];
multiset<int>
st;

int main() {
scanf("%d", &n);
for(int i = 0; i < n; ++i)
scanf("%d", a + i);
for(int i = 0; i < n; ++i)
scanf("%d", b + i), st.insert(b[i]);

for(int i = 0, need; i < n; ++i) {
need = n - a[i];
multiset<int>
::iterator it = st.lower_bound(need);
if(it == st.end())
it = st.begin();

printf("%s%d", i == 0 ? "" : " ", (a[i] + (*it)) % n);

st.erase(it);
}

puts("");

return 0;
}
Copy The Code &

Input

cmd
4
0 1 2 1
3 2 1 1

Output

cmd
1 0 0 2