Concentric spheres

Question

Two different lists having radii of upper hemisphere and lower hemisphere is provided. The first list consists of N upper hemispheres indexed 1 to N and the second has M lower hemispheres indexed 1 to M. A sphere of radius of R can be made taking one upper half of the radius R and one lower half of the radius R. Also, you can put a sphere into a bigger one and create a sequence of nested concentric spheres. But you can't put two or more spheres directly into another one.

If there is a sequence of (D+1) nested spheres, we can call this sequence as a D-sequence.

Find out how many different X-sequence are possible (1 <= X <= C). An X sequence is different from another if the index of any of the hemisphere used in one X-sequence is different from the other.

INPUT

The first line contains a three integers: N denoting the number of upper sphere halves, M denoting the number of lower sphere halves and C.

The second line contains N space-separated integers denoting the radii of upper hemispheres.

The third line contains M space-separated integers denoting the radii of lower hemispheres.

OUTPUT

Output a single line containing C space-separated integers , the number of ways there are to build i-sequence in modulo 1000000007.

Example

Input

3 4 3

1 2 3

1 1 3 2

Output

5 2 0

I am looking for those elements which are part of both the lists of upper as well as lower hemispheres, so that they can form a sphere and then taking their maximum count by comparing their counts in both radii lists.

And, So, for different C sum of products of counts of C+1 elements yields the answer.

How to calculate the above efficiently or is there any other approach ??

Answer 1

Guys this is my first answer. Spare me the whip for now as i am here to learn.

---

You first find the numbers of spheres possible for each radii.

no of spheres: 2 1 1
Having Radii:  1 2 3

Now since we can fit a sphere with radius r inside a sphere with radii R such that R>r, all we need to do is to find the no . of increasing subsequences of length 2,3,...till c in the list of all possible spheres formed.

List of possible spheres:[1,1*,2,3](* used for marking)

consider D1: it has 2 spheres. Try finding the no. of increasing subsequences of length 2 in the above list. They are:

[1,2],[1*,2][1,3][1*,3][2,3]

hence the ans is 5. Get it?? Now how to solve: It can be done by using Dp. Naive solution has complexity .O(n^2*constant). You may follow along the lines as provided in the following link :Dp solution. It is worth mentioning that faster methods do exist which use BIT , segment trees etc.

---

It is similar to this SPOJ problem.