401942: GYM100589 J Three Sorted Arrays

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

J. Three Sorted Arraystime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

This time Laltu wanted the question to be straightforward. So, given 3 1-indexed sorted arrays (A[], B[], C[]), find the number of triplets 1  ≤  i  ≤  j  ≤  k, such that: A[i]  ≤  B[j]  ≤  C[k]. Note that i, j and k don’t exceed the size of respective arrays.

For example, Arrays: A  =  [1, 2, 3, 4] B  =  [5, 6, 7, 8] C  =  [9, 10, 11, 12]

The triplet (i, j, k)  =  (1, 2, 3) has to be considered because: A[1]  ≤  B[2]  ≤  C[3].

Input

First line contains T, the number of test cases. Each test case consists of: P, the length of first array. The next line will consist of P integers. Q, the length of second array. The next line will consist of Q integers. R, the length of third array. The next line will consist of R integers.

Output

For each test case print the required answer in one line.

Constraints

  • 1  ≤  T  ≤  3
  • 1  ≤  P, Q, R  ≤  105
  •  - 109  ≤  Elements of arrays  ≤  109
ExamplesInput
1
3
1 5 6
3
2 3 4
3
7 8 9
Output
6
Note

The possible triplets (i, j, k) are: (1, 1, 1) (1, 1, 2) (1, 1, 3) (1, 2, 2) (1, 2, 3) (1, 3, 3)

加入题单

上一题 下一题 算法标签: