Students_Trees_15.10.2010 - Indices symmetry

Problem I. Indices symmetry ≡

problems
visible spaces
basic formulae
wide text
editor
en ru

Author:	A. Baranov	Time limit:	1 sec
Input file:	Standard input	Memory limit:	256 Mb
Output file:	Standard output

Statement

Young programmer Vasya develops a data storage with a programming interface of multi-dimensional array. Elements of this array are accessed by composite index: (i₁, i₂, …, i_N). Array dimensions are defined by values A₁, A₂, …, A_N (i.e. 0 ≤ i_k < A_k, k = 1… N).

Index ranges are non-decreasing (A_k ≤ A_k + 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.

Given composite index, determine corresponding one-dimensional index.
Given one-dimensional index, determine corresponding composite index.

Input format

Input data starts with an integer N — number of array dimensions.

Followed by N integers A_j — array sizes in each dimension. Next are integer M and M query descriptions, one per line. Queries are of two kinds:

Character f, followed by N integers (i₁, i₂, …, i_N) — composite index.
Character b, followed by an integer — one-dimensional index.

Output format

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.

Constraints

Indexing of both one-dimensional and multi-dimensional arrays starts with zero.

0 ≤ i_j < A_j ≤ 100, A_j ≤ A_j + 1, 1 ≤ N ≤ 10, 1 ≤ M ≤ 10⁵

Sample tests

No. Standard input Standard output

No.	Standard input	Standard output
1	`5 5 5 5 5 5 8 f 4 4 4 4 4 f 0 1 2 3 4 b 125 f 0 1 1 2 2 f 3 1 4 0 2 b 100 b 49 b 0`	`125 49 4 4 4 4 4 39 49 1 3 3 3 3 0 1 2 3 4 0 0 0 0 0`
2	`5 1 2 3 4 5 8 f 0 1 2 3 4 b 27 f 0 1 0 1 3 b 41 b 1 f 0 1 1 2 3 f 0 0 0 0 0 b 0`	`41 0 0 2 3 4 16 0 1 2 3 4 0 0 0 0 1 33 0 0 0 0 0 0`

5 5 5 5 5 5

8
f 4 4 4 4 4
f 0 1 2 3 4
b 125
f 0 1 1 2 2
f 3 1 4 0 2
b 100
b 49
b 0

5 1 2 3 4 5

8
f 0 1 2 3 4
b 27
f 0 1 0 1 3
b 41
b 1
f 0 1 1 2 3
f 0 0 0 0 0
b 0