DCEPC12I - Interview Time

Sidharth Sir is fond of coding. After coding for three years in college, he thought of spreading his knowledge to juniors. He formed a group and named it "CIG" which stands for Coding Interest group. CIG rapidly gained very high reputation. Now, he realizes that its just 4 months left for his graduation. So, he decided to interview students of his group to make them admin of group for coming year. After interviewing more than 50 candidates, he finalized 3 students as admins viz. Aman, Arpit and Sameer.

Sidharth sir has two arrays A and B of size N each. Arrays consist of all unique number such that difference of largest and smallest number is N-1. Just to check their coding skills, Sidharth Sir gives them a task one by one.

He gives Aman 2 numbers X and Y and asks him to return (X^Y) % 2.

Then he gives A and B array to Arpit and also tells him answer given by Aman. Now if Aman’s reply was 1 then B is prioritized array else A is prioritized. Let say prioritized array is P and other one is Q. The task is to first update P. P is updated by following procedure i.e. make a copy of array and sort it. After sorting, update the original as position of each number in sorted array. For example : given is {8, 6, 5, 9, 7} then sorted will be {5, 6, 7, 8, 9} so now updates array will be {4, 2, 1, 5, 3}. And then return an array S such that for all i, S[i] = Q[P[i]]

Then he gives Sameer S array and told him to count the inversions in this array. If i < j and S[i] > S[j] then the pair (i, j) is called an inversion of S.

All the three being very good coders, successfully completed their tasks. Now, here comes your task, you will be given N, arrays A and B, X and Y. You have to output answer told by Sameer.

Input

There is a single positive integer T on the first line of input. It stands for the number of cases to follow. Each case starts with an integer N which stands for number of elements in both arrays. Next line will take N integers of array A i.e. Ais. Next line will take N integers of array B i.e. Bis. And one last line will take two integers X and Y as explained in problem.

Output

For every test case  output one line giving the answer told by Sameer.

Constraints

0 < T <= 10

0 < N < 100000

0 <= Ais, Bis <= 1000000000

0 <= X, Y < 1000000000000000000 (Note: Both X and Y will not be zero.)

Example

Input:
2
1
2
3
4 5
5
5 2 4 3 6
2 3 6 5 4
5 2

Sample Output:
0
5

Explanation

For test case 2:

  • 25 % 2 == 1, so B is priority
  • Now, sorting B → 2, 3, 4, 5, 6
  • so new B = 1, 2, 5, 4, 3
  • so S = 5, 2, 6, 3, 4
  • so there are 5 inversions: 2-5, 3-5, 3-6, 4-5, 4-6

Warning: large input/output data.


Added by:dce coders
Date:2013-12-07
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C C++ 4.3.2 CPP JAVA
Resource:Own Problem

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.