Physical Examination solution codechef

Physical Examination solution codechef

Polycarp plans to undergo a full physical examination at his local clinic. There are n doctors, numbered from 1 to n. The i-th doctor takes patients from minute Li to minute Ri, 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 x and visit all n doctors in some order without waiting or visiting any doctor several times.

More formally, he chooses an integer x and a permutation p1,p2,,pn (a sequence of n integers from 1 to n such that each integer appears exactly once), then proceeds to visit:

  • doctor p1 at minute x;
  • doctor p2 at minute x+1;
  • doctor pn at minute x+n1.

The pi-th doctor should be able to take patients at minute x+i1, so the following should hold: L[pi]x+i1R[pi].

Determine if it’s possible for Polycarp to choose such a minute x and a permutation p that he’ll be able to visit all n doctors in without waiting or visiting any doctor several times. If there are multiple answers, print any of them.

Input Physical Examination solution codechef

The first line contains a single integer t (1t100) — the number of testcases.

Then the descriptions of t testcases follow.

The first line of the testcase contains a single integer n (1n105) — the number of doctors.

The second line of the testcase contains n integers L1,L2,Ln (1Li109).

The third line of the testcase contains n integers R1,R2,Rn (LiRi109).

The sum of n over all testcases doesn’t exceed 105.

Output Physical Examination solution codechef

For each testcase print an answer.

If there exists such a minute x and a permutation p that Polycarp is able to visit all n doctors without waiting or visiting any doctor several times, then print x in the first line and a permutation p in the second line. If there are multiple answers, print any of them.

Otherwise, print 1 in the only line.

Example Physical Examination solution codechef

2 3 1
3 3 2
6 6 5 4 9 4 3 6
7 6 10 6 9 6 6 8
4 2
4 2
2 2 2
3 3 3
output Physical Examination solution codechef

3 1 2 
7 4 6 2 1 8 5 3 
Note Physical Examination solution codechef

In the third testcase it’s impossible to visit all doctors, because Polycarp has to visit doctor 2 at minute 2 and doctor 1 at minute 4. 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 2 minutes. However, since there are three of them, Polycarp can’t visit them all.

Leave a Reply

Your email address will not be published. Required fields are marked *