The University of Waterloo's admission decisions are approaching soon! In a desperate attempt to impress the admissions committee, Jimmy decides to send them a gift, which he would like to wrap up using a ribbon. He has a ribbon of length .
Jimmy puts the ribbon on a number line such that the left end is at , and the right end is at . Each point has a thickness of . There are two ways in which he can fold the ribbon:
L x
: Jimmy holds his finger down at pointx
(as a pivot) and folds whatever is to the left ofx
onto the right side.R x
: Jimmy holds his finger down at pointx
(as a pivot) and folds whatever is to the right ofx
onto the left side.
Note that Jimmy can sometimes fold beyond the left and right edges of the ribbon (see Sample Case 2), but the ribbon will never be folded to a negative coordinate.
After the folding operations that Jimmy performs, determine the final length of the ribbon and the maximum thickness at any point on the ribbon.
Input Specification
First line: (initial length of the ribbon) and (the number of folds).
Next lines: Each line describes a fold of type L
or R
as described above.
Output Specification
Output two space separated integers: the final length of the ribbon and the maximum thickness.
Constraints
For all test cases, , . In addition, will always be a position on the ribbon at the time of folding.
Important Note: for every subtask,
- Outputting the correct final length earns you 30% of the subtask's points.
- Outputting the correct maximum thickness earns you 70% of the subtask's points.
Subtask 1 [30%]
, and there will only be folds of type L
.
Subtask 2 [20%]
Subtask 3 [40%]
Subtask 4 [10%]
No additional constraints.
Sample Input 1:
6 1
L 3
Output for Sample Input 1:
4 2
Explanation for Sample Case 1:
Here is the thickness at every -coordinate at every folding stage (the pivot at each fold is bolded):
Folding stage | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|
Initial (before folding) | 1 | 1 | 1 | 1 | 1 | 1 |
After L 3 fold |
2 | 2 | 1 | 1 |
Therefore, the final length of the ribbon is , and the maximum thickness is .
Sample Input 2:
7 2
L 6
R 9
R 6
Output for Sample Input 2:
3 4
Explanation for Sample Case 2:
Here is the thickness at every -coordinate at every folding stage (the pivot at each fold is bolded):
Folding stage | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
Initial (before folding) | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |||
After L 6 fold |
2 | 2 | 1 | 1 | 1 | |||||
After R 9 fold |
2 | 2 | 1 | 2 | ||||||
After R 6 fold |
2 | 1 | 4 |
Therefore, the final length of the ribbon is , and the maximum thickness is .
Comments