Table Tennis Match

Time limit1sMemory limit1024 MB

Summary

Given the predicted winner of each of N rounds, simulate the table tennis match and print the final score, which stops early once one player leads by 2 points.

Level: Easy2 of 10
Topics: Simulation, Implementation
Solved: No attempts yet

Problem

Dalgu and Phoenix like playing table tennis. Yun-i watches them play again today and decides to predict who will win the match.

The match follows these rules. At the start, both Dalgu and Phoenix have $0$ points. The match consists of $N$ rounds, and the winner of each round gets $1$ point. The match ends when all $N$ rounds are finished or when one player leads by $2$ points during the match. No further rounds are played after that.

Yun-i predicts the winner of each of the $N$ rounds in advance. If Yun-i's predictions come true, find the final score of the match.

Input

The first line contains the number of rounds $N$ ( $1\le N\le 100\ 000$ ).

Each of the next $N$ lines contains a single character, the predicted winner of that round. D means Dalgu is predicted to win, and P means Phoenix is predicted to win.

Output

After the match ends, let the scores of Dalgu and Phoenix be $X$ and $Y$ . Print them in the format X:Y.

Examples2

Example 1
Input
```
5
D
P
P
D
D
```
Expected output
```
3:2
```
Example 2
Input
```
10
D
P
P
D
D
P
P
P
D
D
```
Expected output
```
3:5
```