## Problem I. Indices symmetry ≡

• problems
• 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: (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.

• 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 Aj — 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 (i1, i2, …, iN) — 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 ≤ ij < Aj ≤ 100, Aj ≤ Aj + 1, 1 ≤ N ≤ 10, 1 ≤ M ≤ 105

### Sample tests

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


0.082s 0.015s 13