Mathematics

Time limit2sMemory limit1024 MB

Summary

Given a text with ^ symbols followed by numbers, for each ^ decide whether it can be an exponent and whether it can be a footnote in some split that maximizes the footnote count.

Level: Medium6 of 10
Topics: Implementation, Greedy, Dynamic programming
Solved: No attempts yet

Problem

Even in the wild, you cannot get by without mathematics. To be a good king of the savanna, you must be strong and agile, but also able to divide resources properly, and that requires addition, multiplication, and division. Mufasa knew this, so one day he made Simba read a math book. The book was very hard, and Simba struggled most with the ^ symbol.

In this book, the ^ symbol has two entirely different meanings. The first is exponentiation. The second is footnotes. A footnote is a reference to an explanation of some part of the text, given at the end of the book. In this book, each ^ is followed by a number, and that number is followed by either a punctuation mark (period, comma, colon, or question mark) or a space. Simba knows that the numbers in the footnotes after each ^ are consecutive natural numbers, and the number of the first footnote is 1. Each ^ symbol is either an exponentiation or a footnote.

We consider all possible ways to split the ^ symbols into exponentiations and footnotes. Only the valid splits are those in which the number of footnotes is as large as possible.

For each ^ symbol, Simba wants to know whether it can be an exponentiation in some valid split. Likewise, he wants to know whether it can be a footnote in some valid split.

Input

The only line contains the text of the book. The text has at most $10^6$ characters. It may consist of lowercase and uppercase Latin letters, digits, the ^ symbol, periods, commas, question marks, spaces, and colons. It is guaranteed that each ^ is followed by a natural number (possibly a very large one), and each such number is followed by either a space or a punctuation mark (period, comma, colon, or question mark).

Output

On the first line, print the number of ^ symbols in the text. On the second line, for each ^ symbol, print Y if it can be an exponentiation, and N otherwise. On the third line, for each ^ symbol, print Y if it can be a footnote, and N otherwise.

Hint

The characters before a ^ do not affect whether that symbol is a footnote or an exponentiation.

Examples1

Example 1

Input

sample: 2 plus 2 equals 2^2.^1 easy,^2 isnt it? 1^1 equals 1.

Expected output

4
YNNY
NYYN