Problem I. Indices symmetry ≡

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

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

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

Explanation

Как следует из условия задачи, для заданного набора (i₁, i₂, …, i_N) нас интересует перестановка с минимальным лексикографическим порядком. Все остальные полагаются тождественными и сводятся к ней путем несложной сортировки. В этом случае каждый последующий индекс не может быть меньше предыдущего, т.е. i_k ≤ i_k + 1.

Введем два вспомогательных массива L и M, такие что L[k][j] указывает размер подмассива, содержащего все возможные элементы с составными индексами, у которых первые k − 1 элементов равны нулю, а i_k = j;
M[k][j] указывает позицию элемента с наименьшим составным индексом, удовлетворяющим описанным выше условиям, в одномерном подмассиве.

Для начала рассмотрим случай, когда k = N.

Здесь все кортежи состоят ровно из одного индекса, и можно получить следующую таблицу значений:
L[N][j] = 1, M[N][j] = j, где j = 0, 1, …, (A_N − 1).

Постепенно сдвигаясь к предыдущей размерности, будем использовать следующие формулы:

L[k][j] = L[k + 1][j] + L[k + 1][j + 1] +  ⋯  + L[k + 1][A_k + 1],
т.к. соответствующий подмассив не содержит элементов с индексами, у которых i_k + 1 < j;

M[k][j] = M[k][j − 1] + L[k][j − 1];
M[k][0] = 0.

После заполнения указанных массивов алгоритм вычисления одномерного индекса выглядит так.

В качестве примера будем искать позицию подмассива, содержащего индексы вида (i₁, i₂, …).

Можно легко получить позицию подмассива (i₁, i₁, …), как p₁ = M[1][i₁].

Также можно получить позицию подмассива (0, i₂, …), как p₂ = M[2][i₂].

Однако p₂ также учитывает индексы вида (0, j, …), где j < i₁.

Чтобы исключить их, вычтем из него s = M[2][i₁].

Таким образом, позиция искомого подмассива определяется как p = p₁ + p₂ − s.

Заведем массив S, хранящий позиции с поправками на возрастание индексов:
S[k][i_k] = M[k][i_k] − M[k + 1][i_k],
S[N][i_k] = M[N][i_k].

Последовательно перебирая элементы составного индекса, будем искать сумму значений S[k][i_k].
Т.е. мы постепенно наращиваем наш одномерный индекс, смещаясь на заданную поправку.

Обратная задача восстановления составного индекса по его позиции p происходит так.

Перебирая значения k от меньшего к большему, будем искать в массиве M[k]
наибольшее значение, не превосходящее текущего значения p.
Вместе с этим мы найдем индекс подмассива j,
в котором содержится наш текущий элемент.
Далее вычитаем значение S[k][j] из p.
После этого пройденная часть составного индекса может быть отброшена,
и мы продолжим выполнять те же операции,
но уже в пределах меньшего подмассива.