Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

A. Rock-Paper-Scissors

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputNikephoros and Polycarpus play rock-paper-scissors. The loser gets pinched (not too severely!).

Let us remind you the rules of this game. Rock-paper-scissors is played by two players. In each round the players choose one of three items independently from each other. They show the items with their hands: a rock, scissors or paper. The winner is determined by the following rules: the rock beats the scissors, the scissors beat the paper and the paper beats the rock. If the players choose the same item, the round finishes with a draw.

Nikephoros and Polycarpus have played *n* rounds. In each round the winner gave the loser a friendly pinch and the loser ended up with a fresh and new red spot on his body. If the round finished in a draw, the players did nothing and just played on.

Nikephoros turned out to have worked out the following strategy: before the game began, he chose some sequence of items *A* = (*a*_{1}, *a*_{2}, ..., *a*_{m}), and then he cyclically showed the items from this sequence, starting from the first one. Cyclically means that Nikephoros shows signs in the following order: *a*_{1}, *a*_{2}, ..., *a*_{m}, *a*_{1}, *a*_{2}, ..., *a*_{m}, *a*_{1}, ... and so on. Polycarpus had a similar strategy, only he had his own sequence of items *B* = (*b*_{1}, *b*_{2}, ..., *b*_{k}).

Determine the number of red spots on both players after they've played *n* rounds of the game. You can consider that when the game began, the boys had no red spots on them.

Input

The first line contains integer *n* (1 ≤ *n* ≤ 2·10^{9}) — the number of the game's rounds.

The second line contains sequence *A* as a string of *m* characters and the third line contains sequence *B* as a string of *k* characters (1 ≤ *m*, *k* ≤ 1000). The given lines only contain characters "R", "S" and "P". Character "R" stands for the rock, character "S" represents the scissors and "P" represents the paper.

Output

Print two space-separated integers: the numbers of red spots Nikephoros and Polycarpus have.

Examples

Input

7

RPS

RSPP

Output

3 2

Input

5

RRRRRRRR

R

Output

0 0

Note

In the first sample the game went like this:

- R - R. Draw.
- P - S. Nikephoros loses.
- S - P. Polycarpus loses.
- R - P. Nikephoros loses.
- P - R. Polycarpus loses.
- S - S. Draw.
- R - P. Nikephoros loses.

Thus, in total Nikephoros has 3 losses (and 3 red spots), and Polycarpus only has 2.

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/19/2018 18:36:19 (d1).

Desktop version, switch to mobile version.

User lists

Name |
---|