Psychology has explained the fact that when people play the Rock-Paper-Scissors game, they tend to select moves repetitively. To experiment with this fact, Lucas has designed a Rock-Paper-Scissors game where each player always play the same move.
The game involves two teams, team A (with $$$N$$$ players) and team B (with $$$M$$$ players). Initially, all players are aligned on a straight line. All team $$$A$$$ players are positioned on the left while all team $$$B$$$ players are positioned on the right. Each player has a fixed move in the Rock-Paper-Scissors game, which is either rock, paper or scissors. All players do not change their moves throughout the game.
When the game starts, players will start moving continuously towards the other team, all with a common constant speed. Once two players meet head-to-head, they will play a Rock-Paper-Scissors game with their determined moves. The winner of the Rock-Paper-Scissors game can continue moving while the loser will be eliminated from the game. If there is a draw, the winner will be decided randomly.
You may have noticed that when all players from either team A or team B are eliminated, the remaining players will continue moving forever. Lucas is interested in investigating this scenario. Hence, he asks you to find the number of players from both teams who can possibly survive in the game and keep moving until the death of the universe.
In the Rock-Paper-Scissors game, Rock beats Scissors, Scissors beats Paper and Paper beats Rock. There is a draw if and only if two players make the same move.
The first line consists of 2 integers, $$$N$$$ and $$$M$$$, the number of players initially facing right and left respectively ($$$1 \leq N, M \leq 2 \times 10^5$$$).
The second line consists of a string of length $$$N+M$$$, the $$$i$$$-th character denotes the move of the $$$i$$$-th player. The players are numbered from left to right. It is guaranteed that the string consists of characters R, P and S only, representing rock, paper and scissors respectively.
Output a single integer: the number of players that could possibly survive until the death of the universe.
2 3 SSPRP
2
3 3 PRPSPR
3
In the first sample, 2 players are initially facing the right and 3 players are initially facing the left. The following figure shows the initial positions of the players.
Then, the players start moving towards the other team. Player 2 (holding scissors) first meets player 3 (holding paper). As scissors beats paper, player 3 is eliminated from the game and player 2 can continue moving.
After 2 more rounds, we can conclude that player 4 (holding rock) and player 5 (holding paper) always survive. Thus, the answer is 2.
In the second sample, consider the following state:
If player 1 from team A wins, player 1 will survive eventually. Otherwise, if player 5 from team B wins, player 5 and player 6 will survive eventually. Therefore, the answer is 3.
