Segments on the Line Return-2
When developing a program to verify a participant's solution to the previous problem "Segments on a Line Return" (please refer to its description!), the jury faced challenges that were more complex than the problem itself. With the thought "why not?", it was decided to include the creation of such a verification program in the task set as well.
The verification program has access to three sets of information:
The input data as described in the previous problem's conditions;
The answer provided by an abstract participant, formatted as specified in the previous problem;
The jury's answer.
Your task is to write a program that uses this data to determine whether the abstract participant's solution is correct.
Input
The input consists of three parts. The first part begins with the number N (1 ≤ N ≤ 100000), followed by N pairs a_i, b_i (-10^9 ≤ a_i < b_i ≤ 10^9). Next, there are N numbers, each ranging from 0 to N, where the i-th number indicates the segment that directly contains the i-th segment, or zero, according to the abstract participant. Finally, there are another N numbers in the same format, representing the jury's answer to the problem.
The input data is always correct. This means, for instance, that the participant's answer does not need to be checked for format compliance, and the jury's answer is guaranteed to be correct.
Output
Print N lines. On the i-th line, output OK if the abstract participant's answer for the i-th segment is correct, and WA if it is not.