D. Dilemma of Movies
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Amós, Carlos, and Eduarda like to have movie nights at Carlos's house. On these movie nights, Carlos invites his $$$M$$$ friends (including Amós and Eduarda, since Carlos is the owner of the house). For the session, they need to choose which movies to watch from a collection of $$$N$$$ available titles. The selection can contain any number of movies, including none.

Each of the $$$N$$$ friends has two opinions about the available movies. The opinions are of the type "movie $$$i$$$ is good" or "movie $$$i$$$ is bad." Your task is to choose a set of movies to watch so that at least one of each friend's two opinions is satisfied.

An opinion is satisfied if a movie that the friend considers "good" is included in the selection, or if a movie that the friend considers "bad" is left out.

Input

The first line of input contains the integers $$$N$$$ ($$$2 \leq N \leq 10^{5}$$$) and $$$M$$$ ($$$2 \leq M \leq 10^{5}$$$), the number of friends and the number of movies, respectively.

The following $$$N$$$ lines of input contain the friends' suggestions. Each line contains two opinions, where each opinion has the form "S $$$i$$$" (movie $$$i$$$ is good) or "N $$$i$$$" (movie $$$i$$$ is bad), where $$$i$$$ is an integer with $$$1 \le i \le M$$$.

Output

Print a line with $$$M$$$ letters, for each movie "S" if it is included and "N" if it is not. If there are multiple solutions, print any one of them.

If there is no solution, print "IMPOSSIVEL".

Examples
Input
3 5
S 1 S 2
N 1 S 3
S 4 N 2
Output
N S S S N
Input
2 6
N 3 S 6
N 6 S 3
Output
N N N N N N
Input
4 2
N 1 S 2
N 2 S 1
N 1 N 1
S 2 S 2
Output
IMPOSSIVEL