Cake Cutting

Juseong is preparing a birthday party. Instead of an ordinary cake, he got a roll cake, which he has always liked. The roll cake has decorations, so it can be cut only at certain positions. Juseong wants to prepare as many pieces of the roll cake as the number of friends coming to the party, and he decided to find out the size of the smallest piece in advance. But his mischievous friends will not tell him directly how many people are attending. So he writes several numbers in a list, and for each number he wants to find the maximum possible length of the smallest piece when the cake is cut into that many pieces.

For example, suppose a roll cake of length 70cm can be cut at 5 positions (10cm, 20cm, 35cm, 55cm, 60cm). If one of the numbers in the list is 3, the maximum possible length of the smallest piece is 15cm. It is achieved by cutting at 20cm, 35cm, and 55cm.

The first line gives N, the length of the list of cut counts, M, the number of positions where the cake can be cut, and the integer L, the length of the roll cake. (1 ≤ N ≤ M ≤ 1,000, 1 < L ≤ 4,000,000)

The next M lines give integers Si, the positions where the cake can be cut. (1 ≤ Si < L)

The next N lines give integers Qi, the cut counts. (1 ≤ Qi ≤ M)

The Si are given in increasing order with no duplicates, and the same holds for the Qi.

For each of the N cut counts, output on its own line the maximum possible length of the smallest piece when the roll cake is cut that many times.