UT Invitational Programming Contest Fall 2019

Start

2019-11-23 19:00 UTC

UT Invitational Programming Contest Fall 2019

End

2019-11-24 00:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -86 days 23:39:55

Time elapsed

5:00:00

Time remaining

0:00:00

Problem A
Bump, Set, Spike!

Volleyball season is starting at your local recreational center! This means all kinds of volleyball leagues are about to be in full swing: leagues for youths, seniors, amateurs, and so on. The most prestigious and highly contested league at the rec center is the Premier Adult Coed Volleyball League. In recent years, the prestige of the league has become problematic, as all the top referees have opted to shirk their duties and compete as players, leaving only sub-par referees to oversee league matches.

To combat this, league organizers have proposed the possibility of a computer program that can play the role of referee. The games are played by typical volleyball rules: there are two teams consisting of six players each, and the program is to determine that the rallies between the two teams are valid. More specifically, for each rally, a sequential record of who touches the ball is streamed to the program, and from that it should be determined in real-time if there are any violations of the following rules:

  1. A player cannot touch the ball twice in a row.

  2. A team cannot touch the ball more than three times in a row.

  3. If a team touches the ball twice or more before it is hit to the other team, both a man and a woman must have touched the ball at least once. A ball is considered to be “hit to the other team” once the other team makes contact with the ball, OR at the end of a rally. For example, if a rally ends with three consecutive hits from women on team A, that is a violation.

Other violations, such as net touches, carries, or the ball landing out of bounds will still be called by human referees, so the program need not worry about those.

The league organizers have come to you for help in creating this program. The ball is in your court!

Input

The first line contains a single integer $N$ $(2 \leq N \leq 10^5)$, the number of touches in the rally. Then follows $N$ lines, with the $i$th line describing the $i$th touch in the rally. Each of the $N$ lines will contain a string consisting of three characters. The first character will be either A or B, denoting the team that touched the ball. The second character will be one of $1$, $2$, $3$, $4$, $5$, or $6$, denoting the specific player on the team that touched the ball. The final character will be either W or M, denoting whether the player that touched the ball was a man or a woman. Throughout a rally, the gender of players is guaranteed to remain consistent.

Output

If there was a violation in the rally, print either A or B: whichever team was first to commit a violation. If there was no violation, print No violation.

Sample Input 1 Sample Output 1
3
A1M
A1M
B5W
A
Sample Input 2 Sample Output 2
3
A1M
A2M
B2M
A
Sample Input 3 Sample Output 3
5
A4W
A5W
A1M
B3M
A2M
No violation