After wrapping a present for her friend's birthday, Elaine discovered that she has a long length of ribbon left over. The ribbon is currently unwound, so she decided that she will fold the ribbon times before putting it away in a small box. To make sure the ribbon will fit, she would like to know what the length and thickness of the ribbon will be once she performs her sequence of folds.
The ribbon initially has a length of units and a thickness of unit. When folding a ribbon at a point from the left, the part of the ribbon left of is folded onto the part of the ribbon right of . Formally, for all , the thickness of the ribbon at the point is added to the thickness at the point and the thickness at the point becomes zero. Folding the ribbon from the right is the same up to symmetry.
The thickness of the ribbon is defined as the maximum thickness of any given point. The length of the ribbon is defined as the number of points with non-zero thickness. Given the sequence of folds, can you help Elaine determine the dimensions of the final ribbon?
Input Specification
The input will contain 10 datasets. Each dataset begins with two integers , (, ), the initial length of the ribbon and the number of folds. The points of the ribbon are numbered from to .
The next lines each contain an integer () followed by either L
or R
, representing a fold at point from either the left or right. The point is guaranteed to be at a point with non-zero thickness.
For the first 3 cases, each fold will be of type L
.
For the first 6 cases, .
Output Specification
For each dataset, output two space-separated integers: the length and thickness of the ribbon.
Sample Input (Two Datasets Shown)
6 1
3 L
10 2
10 L
10 R
Sample Output
4 2
8 3
Explanation of Sample Datasets
In the first dataset, the thickness of the ribbon at each point is .
In the second dataset, the thickness of the ribbon at each point is .
Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org
Comments