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 aren
atoms of the element represented byE
. 
( A ) n
, whereA
is a valid chemical formula, indicating that the number of atoms of each element inA
must be multiplied byn
. 
A B
, whereA
andB
are valid chemical formulas. The number of atoms of each elementE
in equals the number of atoms ofE
inA
plus the number of atoms ofE
inB
.
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?
Constraints
Subtask 1 [50%]
Subtask 2 [50%]
Input Specification
The first line contains one integer, .
The second line contains a valid chemical formula consisting of spaceseparated components.
Output Specification
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
Comments