Problem I. Indices symmetry

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.

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:

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.090s 0.010s 13