Physical Examination solution codechef
Polycarp plans to undergo a full physical examination at his local clinic. There are doctors, numbered from to . The -th doctor takes patients from minute to minute , so Polycarp can visit him at any minute in this range. It takes each doctor exactly one minute to examine Polycarp’s health.
Polycarp wants to arrive at the clinic at some minute and visit all doctors in some order without waiting or visiting any doctor several times.
More formally, he chooses an integer and a permutation (a sequence of integers from to such that each integer appears exactly once), then proceeds to visit:
- doctor at minute ;
- doctor at minute ;
- doctor at minute .
The -th doctor should be able to take patients at minute , so the following should hold: .
Determine if it’s possible for Polycarp to choose such a minute and a permutation that he’ll be able to visit all doctors in without waiting or visiting any doctor several times. If there are multiple answers, print any of them.
The first line contains a single integer () — the number of testcases.
Then the descriptions of testcases follow.
The first line of the testcase contains a single integer () — the number of doctors.
The second line of the testcase contains integers ().
The third line of the testcase contains integers ().
The sum of over all testcases doesn’t exceed .
For each testcase print an answer.
If there exists such a minute and a permutation that Polycarp is able to visit all doctors without waiting or visiting any doctor several times, then print in the first line and a permutation in the second line. If there are multiple answers, print any of them.
Otherwise, print in the only line.
In the third testcase it’s impossible to visit all doctors, because Polycarp has to visit doctor at minute and doctor at minute . However, that would require him to wait a minute between the visits, which is not allowed.
In the fourth testcase all doctors take patients in the span of minutes. However, since there are three of them, Polycarp can’t visit them all.