Holi Clash at Amazon

hard

The festival of Holi is being celebrated at Amazon, where two rival teams—AWS and Prime—are competing in a special color-throwing game.

The players line up in a row, each belonging to either team A (AWS) or team P (Prime). During each turn, players act in order from first to last. When it's a player's turn, they can do one of the following:

  • Color an opponent: The player can throw color on any non-colored player from the opposing team, removing them from all future turns.
  • Declare victory: If a player notices that all remaining non-colored players belong to their team, they can immediately declare victory and their team wins the Holi celebration rights.

You're given a string players representing each person's team. The character 'A' represents AWS and 'P' represents Prime. The number of characters in the string equals the number of players.

The game proceeds from the first player to the last, skipping any players who have been colored. Assume every player uses optimal strategy to help their team win.

Predict which team will eventually declare victory. The output should be either "AWS" or "Prime".

Input Format:

The first and only line contains the string players. 1players3000001 \leq |players| \leq 300000

Output Format:

Output a single string containing either "AWS" or "Prime".

Examples:

Example 1:

Input:

AP

Output:

AWS

Example 2:

Input:

APP

Output:

Prime

Code

Loading Editor...