01204212/id request

This is part of 01204212

An API requires every user to have a unique ID. To ensure that it provides an interface to check and allocate IDs. There are N requests; each request specifies an ID x, which is an integer from 0 up to 1,000,000,000. For each request, your program have to answer if x has been used. In the case where x is new, it allocates that integer for the requested user. Initially, no ID has been used.

Input

• First line: an integer N (1<=N<=100,000)
• The next N lines: each line contains an integer x

Output

There are N lines of output, each contains either Y (if the requested ID has been used before) or N (if the requested ID is new)

Example

Input

10
4
2
4
10
100
30
10
35
100
200

Output

N
N
Y
N
N
N
Y
N
Y
N