# Double inversions Solution

Problem

Consider a certain permutation of integers from $1$ to $�$ as $�=\left\{{�}_{1},{�}_{2},...,{�}_{�}\right\}$ and reverse of array $�$ as $�$, that is, $�=\left\{{�}_{�},{�}_{�-1},...,{�}_{1}\right\}$. You are given the inversions at each position of array $�$ and $�$ as $\left\{�{�}_{1},�{�}_{2},\dots ..,�{�}_{�}\right\}$ and $\left\{�{�}_{1},�{�}_{2},\dots ..,�{�}_{�}\right\}$ respectively.

Find the original array $�$. If, there are multiple solutions, print any of them. If there is no solution, then print -1.

Note: The inversion of array $���$ for position $�$ is defined as the count of positions $�$ satisfying the following condition $��{�}_{�}>��{�}_{�}$ and $1\le �<�$.

Input format

• The first line contains $�$ denoting the number of test cases.
• For each test case:
• The first line contains $�$ denoting the number of elements.
• The second line contains the elements $\left\{�{�}_{1},�{�}_{2},\dots ..,�{�}_{�}\right\}$.
• The third line contains the elements $\left\{�{�}_{1},�{�}_{2},\dots ..,�{�}_{�}\right\}$.

Output format

For each test case, print the array $�$ in the space-separated format or -1 if no solution exists. Each test case should be answered in a new line.

Constraints

Sample Input
2
4
0 0 2 3
0 0 0 1
3
0 2 1
2 1 0
Sample Output
3 4 2 1
-1
Time Limit: 3
Memory Limit: 256
Source Limit:
Explanation

For first test case

Consider permutation $�=\left\{3,4,2,1\right\}$.

It can be seen that inversion for this array will be $��=\left\{0,0,2,3\right\}$ as:

•  For i = 1, no positions satisfy   $��{�}_{�}>��{�}_{�}$ and $1\le �<�$.
•  For i = 2, no position satisfy   $��{�}_{�}>��{�}_{�}$ and $1\le �<�$.
•  For i = 3, j = 1, 2 satisfy   $��{�}_{�}>��{�}_{�}$ and $1\le �<�$.
•  For i = 4, j = 1, 2, 3 no positions satisfy   $��{�}_{�}>��{�}_{�}$ and $1\le �<�$.

Now, $�=\left\{1,2,4,3\right\}$.

It can be seen that inversion for this array will be $��=\left\{0,0,0,1\right\}$ as:

•  For i = 1, no positions satisfy   $��{�}_{�}>��{�}_{�}$ and $1\le �<�$.
•  For i = 2, no positions satisfy   $��{�}_{�}>��{�}_{�}$ and $1\le �<�$.
•  For i = 3,  no positions satisfy   $��{�}_{�}>��{�}_{�}$ and $1\le �<�$.
•  For i = 4, j = 3 satisfy   $��{�}_{�}>��{�}_{�}$ and $1\le �<�$.

Thus, $�=\left\{3,4,2,1\right\}$ is a valid permutation.

## Bitwise AND sumBitwise AND sum Solution(C++):-

#include <iostream>
#include <limits>
#include <vector>
using namespace std;
#define MAX_N 100000
void execTestcase(
int n,
vector<int>& arr,
vector<int>& iA,
vector<bool>& occupations
);
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
vector<int> arr, iA;
vector<bool> occupations;
arr.reserve(MAX_N);
iA.reserve(MAX_N);
occupations.reserve(MAX_N);
for (int i = 0; i < t; i++) {
int n;
cin >> n;
arr.resize(n);
iA.resize(n);
occupations.resize(n);
execTestcase(n, arr, iA, occupations);
}
return 0;
}
void execTestcase(
int n,
vector<int>& arr,
vector<int>& iA,
vector<bool>& occupations
) {
// scan IA and init occupasions
for (int i = 0; i < n; i++) {
int v;
cin >> v;
iA[i] = v;
occupations[i] = false;
}
// scan IR, calculate A and eventually fail if not a solution
bool isSolution = true;
for (int i = n - 1; i >= 0; i--) {
int iR;
cin >> iR;
arr[i] = n - iA[i] - iR;
isSolution = isSolution &&
(arr[i] > 0) &&
!occupations[(arr[i] + n) % n];
occupations[(arr[i] + n) % n] = true;
i *= isSolution;
}
cin.ignore(numeric_limits<streamsize>::max(), '\n');
// print solution
if (isSolution) {
for (auto a : arr) {
cout << a << " ";
}
cout << endl;
} else {
cout << "-1" << endl;
}
}