Description

There are two arrays a, b of length n, where a_i = i, i = 1, 2, ..., n. Also, you have another array c which is empty at the beginning.

Your task is to transform c into b, using the following operations:

1. Push the first element of a into the stack, and delete it in a
2. Append the top element of the stack to the last element of c, and pop it out of the stack

It is guaranteed that there always exists a series of operation that can transform c into b.

Input

The first line contains an integer n, representing the length of a and b. The second line contains n integers b₁, b₂, ..., b_n.

Constrain

• 1 <= n <= 1000
• 1 <= b_i <= n, i = 1, 2, ..., n
• If i ≠ j, b_i ≠ b_j

Output

Output 2n lines. If the i-th operation is the first type, output "Push" (without quote) in the i-th lines; otherwise, output "Pop" (without quote).

It can be shown that the seires of the operations are unique, and we always need 2n operations to complete the task.

Hint

For the sample testcase, the following shows the content of a, c, and stack after each operation:

Operation	a	c	stack
1	2, 3, 4		1
2	3, 4		1, 2
3	4		1, 2, 3
4	4	3	1, 2
5	4	3, 2	1
6		3, 2	1, 4
7		3, 2, 4	1
8		3, 2, 4, 1

Sample Input  Download

Sample Output  Download

Tags

Discuss