Trong một thế giới cổ đại đầy bí ẩn, có một loại rương báu đặc biệt, chỉ có thể mở được bằng một dãy ký hiệu đặc biệt. Những chiếc rương này do các bậc tiền nhân để lại, bên trong chứa đầy châu báu. Nhi là một nhà thám hiểm dũng cảm, trong một chuyến phiêu lưu cô đã tìm thấy những chiếc rương bí ẩn này và phát hiện ra quy tắc để mở rương:

1. Dãy ký hiệu rỗng là hợp lệ;

2. Nếu A và B hợp lệ, thì AB cũng hợp lệ;

3. Nếu A hợp lệ, thì (A) và [A] cũng hợp lệ.

Bây giờ, Nhi đang có trong tay một dãy ký hiệu, cô muốn biết dãy ký hiệu này có hợp lệ hay không, tức là cô có thể dùng nó để mở rương hay không. Bạn có thể giúp cô ấy không?

Dữ liệu vào

Dữ liệu vào là một xâu chỉ gồm các ký tự (, ), [, ], { và }, biểu diễn một dãy ký hiệu, độ dài không vượt quá $10^5$ .

Dữ liệu ra

In ra một dòng, nếu dãy ký hiệu tương ứng là hợp lệ thì in ra \"Y\", ngược lại in ra \"N\".

Ví dụ 1

Input

([])

Output

Y

Ví dụ 2

Input

([(])

Output

N