The Great Circus

All submissions for this problem are available.
The Great Circus has come to Pilani. It is an amazing circus with lots of funny clowns, daredevil stuntsmen, magicians, performers and amazing animals. But with all this success comes a lot of workload. Thus the circusmaster has decided to hire you as an assistant to help him with all the different problems he will face.
The circus is being setup in the Pilani. The fences have been setup by the elephants. Now the circusmaster has allocated the job of painting the whole fence to the head clown.
The unpainted fence has N planks. The planks are numbered from 1 to N. The circusmaster has given the clown C buckets of paint, each of a different color. The colors are numbered from 1 to C. Since the clown is fat and lazy, he just wants to lie down outside and enjoy the sun. So he instead orders M monkeys to do his job.
The monkeys make a line and take turns painting the fence. In each turn, the painter monkey randomly chooses a nonempty segment of the fence (a segment is a contiguous sequence of planks of the fence) and paints all planks in that segment with his/her favorite color. The random choice is made in such a way that the probability of selecting any nonempty segment is the same.
Now the clown wonders how the fence will look like after the monkeys finish painting it. He already knows the order in which monkeys will paint and he knows each monkey's favorite color. Since he knows that you are a good assistant, he asks for your help. He will shout out to you Q times . Each time he will tell you a color and the plank numbers of the start and end of a segment. You have to tell him the expected number of planks which have that color in that segment.
Input
The first line of each test case contains 3 integers N, C and M (number of planks, number of colors and number of monkeys respectively).
The next line contains M spaceseparated integers. The i^{th} integer is the favorite color of the i^{th} painter.
The next line contains a single integer Q, the number of times the circusmaster shouted out to you.
The next Q lines contain 3 spaceseparated integers each, the first and last plank numbers of a segment and a color.
Output
For each of the Q shout outs to you, output the expected number of planks in that segment with that color.
Answer should have relative and absolute accuracy of at least 10^{6}.
Constraints
1 ≤ N,M,C ≤ 100
1 ≤ Q ≤ 200000
Sample input
2 1 1
1
1
1 2 1
Sample output
1.33333333
Explanation
There are 2 planks. There are 3 segments (the left plank, the right plank, both planks). We have to find out the expected number of painted segments (there is just one color in this test case and the given segment covers the whole fence). That is equal to the sum of number of painted planks multiplied by the probability of having that many painted planks.
Let f(i) = Probability that i planks are painted = (number of segments of length i)/(total number of segments)
f(1) = 2/3, f(2) = 1/3
Result = 1*f(1) + 2*f(2) = 2/3 + 2/3 = 4/3 = 1.33333...
Note
Fast IO required
Author:  sourabh13 
Tags  sourabh13 
Date Added:  26022016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, RUBY, PYP3 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 