H. Закулисье регулярности
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы застряли в Закулисье регулярности — измерении, напоминающем обычное Закулисье, но подчиняющемся своим особым правилам. К счастью, вам повезло, и вам попался блокнот с описанием того, как проходить различные комнаты, и планом побега.

Всего существует $$$n$$$ типов комнат. Для каждого типа известно, сколько минут занимает прохождение этой комнаты. План побега — это строка. Каждая из первых $$$n$$$ заглавных букв латинского алфавита обозначает комнату и сама по себе является корректным планом побега. Пусть $$$s$$$, $$$f$$$ — корректные планы побега, тогда:

  • $$$s f$$$ — корректный план побега, это означает, что надо пройти план $$$s$$$, затем $$$f$$$.
  • $$$s \, | \, f$$$ — корректный план побега, это означает, что надо пройти ровно один из планов $$$s$$$, $$$f$$$, причём альтернатив может быть сколь угодно много. У $$$|$$$ приоритет меньше, чем у конкатенации (предыдущего правила).
  • $$$(s)$$$ — корректный план побега, это означает, что надо пройти $$$s$$$ один раз. (Скобки служат той же цели, что и в математических выражениях).
  • $$$(s)x$$$ — после скобок может идти число $$$x$$$ от 2 до 9 включительно, это означает, что нужно пройти план $$$s$$$ ровно $$$x$$$ раз, причём не обязательно все разы одинаково.

Пока вы ещё в шоке от случившегося и не приступили к исполнению плана, рассчитайте, сколько минимум и максимум вы можете бродить по Закулисью, следуя плану. Либо определите, что бродить вам столь долго, что не отличимо от вечности...

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ — количество наборов входных данных $$$(1 \leq t \leq 10^4)$$$. Далее следует описание наборов входных данных.

В первой строке вводится целое число $$$n$$$ — количество различных типов комнат в Закулисье. $$$(1 \leq n \leq 26)$$$.

Во второй строке вводятся $$$n$$$ целых чисел $$$a_i$$$ — длительность прохождения комнаты типа $$$i$$$ $$$(1 \leq a_i \leq 1000)$$$;

В третьей строке вводится строка $$$P$$$ — сам план. Гарантируется, что план соответствует описанному формату $$$(1 \leq |P| \leq 10^5)$$$.

Гарантируется, что сумма длин строк $$$|P|$$$ по всем наборам не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите два целых числа — минимум и максимум, сколько может продлиться исполнение плана побега. Если минимум или максимум строго больше чем $$$10^{16}$$$, выведите вместо этого числа строку «inf».

Пример
Входные данные
4
3
1 2 3
A|B
3
3 2 1
A(B|C)3
1
4
(A(AA|A(A)9A)|AAA)2
1
100
((((((((((((((((A)9)9)9)9)9)9)9)9)9)9)9)9)9)9)9)9
Выходные данные
1 2
6 9
24 96
inf inf