Author: | A. Baranov | Time limit: | 1 sec | |
Input file: | Standard input | Memory limit: | 256 Mb | |
Output file: | Standard output |
Young programmer Vasya develops a data storage with a programming interface of multi-dimensional array. Elements of this array are accessed by composite index: (i1, i2, …, iN). Array dimensions are defined by values A1, A2, …, AN (i.e. 0 ≤ ik < Ak, k = 1… N).
Index ranges are non-decreasing (Ak ≤ Ak + 1). A special feature of Vasya's array is index-permutation symmetry. It means that elements with composite indices coinciding up to their permutation are considered equal.
To compactly represent array in memory Vasya decided on the following layout. Elements are stored sequentially row-by-row (aka row-major order) in one-dimensional array, which corresponds to lexicographically increasing composite indices. Those elements for which some permutation of their composite index was already encountered before are skipped.
Your program must execute queries of two kinds.
Input data starts with an integer N — number of array dimensions.
Followed by N integers Aj — array sizes in each dimension. Next are integer M and M query descriptions, one per line. Queries are of two kinds:
Output must contain a sequence of integers — result of execution for each query in the order of input. Elements of composite indices must be sorted in ascending order.
Indexing of both one-dimensional and multi-dimensional arrays starts with zero.
0 ≤ ij < Aj ≤ 100, Aj ≤ Aj + 1, 1 ≤ N ≤ 10, 1 ≤ M ≤ 105
No. | Standard input | Standard output |
---|---|---|
1 |
|
|
2 |
|
|