A chemical formula is a way of presenting information about the elements present in a molecule. Each distinct element in the formula is uniquely represented by a symbol, a string consisting either of one uppercase English letter or one uppercase followed by one lowercase English letter. There are three types of components that may be present in a chemical formula:
E n, a valid symbol followed by a positive integer no greater than .
(, an opening parenthesis.
) n, a closing parenthesis followed by a positive integer no greater than .
A chemical formula is valid if and only if:
E n, indicating that there are
natoms of the element represented by
( A ) n, where
Ais a valid chemical formula, indicating that the number of atoms of each element in
Amust be multiplied by
A B, where
Bare valid chemical formulas. The number of atoms of each element
Ein equals the number of atoms of
Aplus the number of atoms of
Dr. Henri is observing a chemical formula made of components and wants to know the number of atoms of each element present in it. Since these numbers may be very large, he would like to know their values mod . Can you help him?
Subtask 1 [50%]
Subtask 2 [50%]
The first line contains one integer, .
The second line contains a valid chemical formula consisting of space-separated components.
Output lines, where is the number of distinct elements present in the formula. Each line should be of the form
a b, where
a is the symbol of the element and
b is the number of atoms of that element mod . Please output the symbols in lexicographically increasing order.
Sample Input 1
4 ( C 1 Cl 4 ) 2
Sample Output 1
C 2 Cl 8
Sample Input 2
8 ( Co 1 ( N 1 H 3 ) 6 ) 2 Cl 3
Sample Output 2
Cl 3 Co 2 H 36 N 12