## 2-D Permutations

View as PDF

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 1G

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 . Call an arrangement 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.

#### Input Specification

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 Specification

Output lines, the th line containing the number of different cells can be placed in all valid arrangements.

#### Constraints

No further 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:

 1 2 3 4
 1 3 2 4

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:

 1 2 3

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

11

#### 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: