Ramu has an array A of size N (N is even) consisting of numbers from 0 to N-1 in it and a permutation array P of size N initially that is a permutation of A. (eg: 3 1 2 0 is a permutation array of size 4). He does the following steps until N is 2 :
- He rearranges the array A based on the permutation array as A[i] = A[P[i]] (0 based indexing).
- He then deletes 2 numbers from the array A with indices (0-based) N∗a2b and N(a+b)2b where N is the current size of the array and a and b are given. He takes the floor of the numbers if they are not integers where floor is the greatest integer less than or equal to the number.
- He deletes the numbers (not indices) N-1 and N-2 from the permutation array P keeping the remaining elements of the array P in same order thus making both P and A the same size (N-2).
- He reduces N by 2 and repeats the same process until only 2 numbers are left in the array A.
Given N, initial permutation array, a and b find the last 2 numbers in the same order as they appear in the final array A.
Input Format:
The first line of input contains a single integer N denoting the initial size of A.
The next line contains a permutation array of size N with numbers from 0 to N−1 permuted.
The last line contains 2 space seperated integers a and b respectively.
Constraints:
2≤N≤105
0≤P[i]≤N−1 ∀ 0≤i≤N−1
0≤a<b≤109
N is even
Output Format:
Print 2 space seperated integers denoting the last 2 elements in the same order as the final array A.
Initially, A is 0 1 2 3 4 5 and P is 0 4 2 3 5 1
After Permuting (Applying A[i] = A[P[i]]):
A becomes 0 4 2 3 5 1
Then we delete (6∗3)(2∗4)th and (6∗(3+4))(2∗4)th element (0-indexing), which are the 2nd and 5th(Floor(5.25)) element respectively.
Therefore, A becomes 0 4 3 5, P becomes 0 2 3 1 (after deleting 4 and 5 from P)
Repeating the same steps:
A becomes 0 3 5 4 after permuting.
A becomes 0 5 after deleting 1st and 3rd element and P becomes 0 1 (after deleting 2 and 3).
Thus, the last 2 elements are are 0 and 5 in that order.
