D. 38 parrots
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There is an iconic Russian animated cartoon about a constrictor whose length equals to $$$5$$$ monkeys, $$$2$$$ little elephants or $$$38$$$ parrots plus one parrot wing because animals are not familiar with the metric system. Doctor Dolittle wants to check whether it is possible to find an appropriate unit of measurement for the patients waiting in queue to see him. The doctor spends most of his working hours treating the patients so he can only do the measurements during his leisure time.

When animals come to see the doctor, they wait in queue. Once a new patient joins the queue, the doctor's assistant measures his or her length and writes the result down in a list. Reception is in order of turn. Once the patient leaves, he or she is crossed out from the list. Every now and then, Doctor Dolittle checks the list and tries to find an animal that can be used to measure everyone else (not crossed out yet) so that their lengths would be positive integers.

Write a program to help Doctor Dolittle!

Input

The first line contains a value of $$$n$$$ ($$$1 \le n \le 10^5$$$) – the number of manipulations with the patients list.

The next $$$n$$$ lines contain one specific manipulation with the patients list. Three types of manipulations are possible:

  • Enqueueing the patient to the list – a line that starts with the «+» (plus) symbol followed by the length of the new patient (without spaces)
  • Dequeueing the patient from the list – a line containing a single symbol «–» (minus)
  • Searching for a patient that could serve as a common unit of measurement – a line containing a single symbol «?» (question mark). This manipulation applied for nonempty list only.

The length of the patient is a positive integer not exceeding $$$10^9$$$.

Output

The output file must contain exactly one line for every search. If the list contains an animal that can be used to measure all other animals on the list, the line must start with a capital letter «Y» followed by the length of that animal. If there is no suitable animal on the list, the line must contain a capital letter «N.»

Examples
Input
10
+4
+2
?
+3
?
-
-
?
+1
?
Output
Y2
N
Y3
Y1
Input
2
+5
?
Output
Y5