PPAP

Interview

Time limit1sMemory limit512 MB

Summary

Decide whether a length-1000000 string of P and A is generated from P by replacing a P with PPAP at each step.

Level: Medium5 of 10
Topics: Stack, String, Greedy
Solved: No attempts yet

Problem

bryan likes PPAP. While thinking about how to spread PPAP to people, bryan came up with the PPAP string.

A PPAP string is defined as a string that can be made by starting from the string P and repeatedly replacing a P in the string with PPAP. More precisely, it is defined as follows.

P is a PPAP string.
A string obtained by replacing one P in a PPAP string with PPAP is a PPAP string.

For example, PPAP is a PPAP string. Also, PPPAPAP, obtained by replacing the second P of PPAP with PPAP, is a PPAP string.

Given a string, write a program that tells whether this string is a PPAP string.

Input

The first line gives a string. The string consists only of the uppercase letters P and A, and its length is between 1 and 1,000,000.

Output

On the first line, print PPAP if the given string is a PPAP string, and NP otherwise.

Examples2

Example 1
Input
```
PPPAPAP
```
Expected output
```
PPAP
```
Example 2
Input
```
PPAPAPP
```
Expected output
```
NP
```