Задача I. Indices symmetry ≡

Условие

Молодой программист Вася разрабатывает хранилище данных, имеющее программный интерфейс многомерного массива. Доступ к элементам в таком массиве осуществляется по их составным индексам: (i₁, i₂, …, i_N). Размерность массива определяется значениями A₁, A₂, …, A_N (то есть 0 ≤ i_k < A_k, k = 1… N).

Диапазоны изменения индексов не убывают (A_k ≤ A_k + 1). Особенностью Васиного массива является индексно-перестановочная симметрия. Это означает, что его элементы, составные индексы которых совпадают с точностью до их перестановки, полагаются тождественными.

Для компактного расположения массива в памяти Вася решил использовать следующую схему. Элементы хранятся последовательно в построчном формате (row-major order) в одномерном массиве, что соответствует лексикографическому возрастанию составных индексов. При этом элементы, для которых некоторая перестановка составного индекса встречалась ранее, пропускаются.

Вашей программе требуется выполнять запросы следующих двух видов.

• По заданному составному индексу определить индекс соответствующей ему ячейки в одномерном массиве.
• По заданному одномерному индексу получить соответствующий ему составной индекс.

Формат входных данных

В начале входных данных находится натуральное N — число измерений массива.

Далее следует последовательность из N целых чисел A_j — размеры массива по каждому измерению. За ними следует число M и M описаний запросов, по одному запросу в строке. Запросы могут быть двух видов:

• Символ f, за которым следует N целых чисел (i₁, i₂, …, i_N) — составной индекс.
• Символ b, за которым следует целое число — одномерный индекс.

Формат выходных данных

Выходные данные должны содержать последовательность целых чисел — результаты выполнения каждого запроса, в порядке ввода. Элементы составных индексов должны быть отсортированы в порядке возрастания.

Ограничения

Индексация одномерных и составных индексов по каждому измерению начинается с нуля.

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

Примеры тестов

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