## DMPG '19 S3 - Chemical Counting Capers

View as PDF

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem types

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 n atoms of the element represented by E.
• ( A ) n, where A is a valid chemical formula, indicating that the number of atoms of each element in A must be multiplied by n.
• A B, where A and B are valid chemical formulas. The number of atoms of each element E in equals the number of atoms of E in A plus the number of atoms of E in B.

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?

#### Input Specification

The first line contains one integer, .
The second line contains a valid chemical formula consisting of space-separated 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