Edward spent the whole weekend brainstorming problems involving 2-D arrays. Unfortunately, they were all too hard, so he came up with this instead:
You are given integers, numbered from to . You would like to arrange these numbers into an array . The rows are numbered from to and the columns from to . Denote the number assigned to the -th cell from the top and the -th cell from the left . An arrangement is called valid if for all cells with , , and for all cells with , . You are also given queries. For each query, a number is given, and you must return the number of different cells can be placed in all valid arrangements.
Edward has no idea how to solve this problem either. Please help him solve it.
The first line will contain three integers , , and , the dimensions of the array and the number of queries.
The next lines will each contain one integer , as specified in the problem statement.
Output lines, the -th line containing the number of different cells can be placed in all valid arrangements.
For all subtasks:
Subtask 1 [15%]
Subtask 2 [35%]
Subtask 3 [50%]
No additional constraints.
Sample Input 1
2 2 4 1 2 3 4
Sample Output 1
1 2 2 1
Explanation for Sample 1
The two valid arrangements are:
and can be placed in two different cells, while and can only be placed in one.
Sample Input 2
1 3 3 1 2 3
Sample Output 2
1 1 1
Explanation for Sample 2
The only valid arrangement is:
Since there is only 1 valid arrangement, each number can only be placed in 1 unique cell.
Sample Input 3
5 5 1 18
Sample Output 3
Explanation for Sample 3
The following diagram shows the 11 possible cells can be placed in. Green cells denote possible cells, while red cells denote otherwise: