Математика

К сожалению, даже в дикой природе без математики никуда. Чтобы быть хорошим королем саванны, нужно быть не только сильным и ловким, но и уметь правильно распределить ресурсы, а тут никак не обойтись без сложения, умножения и деления. Это знал и Муфаса, и поэтому в один прекрасный день он заставил Симбу читать книгу по математике. Книга была очень сложной, а сложнее всего Симбе было со знаком ^.

Дело в том, что в этой книге таким знаком обозначено две совсем разные вещи. Во-первых, таким знаком обозначили возведение в степень. Во-вторых --- сноски. Сноски --- это ссылки на объяснения некоторых кусков текста, которые приведены в конце книги. В этой книге после каждого символа ^ следует некоторое число, после которого может быть либо знак препинания, либо пробел. Симба знает, что числа, которые стоят в сносках после символа ^, являются последовательным натуральными числами. Число возле самой первой сноски равно единице. Про каждый символ ^ можно сказать, является ли он возведением в степень или сноской.

Рассмотрим все возможные варианты разбиения знаков ^ на степени и сноски. Будем считать, что авторы учебника постарались объяснить все как можно более подробно, а поэтому, корректными будем считать только те варианты, в которых количество сносок максимально.

Про каждый символ ^ Симба хочет знать, может ли он являтся возведением в степень в каком-нибудь из корректных разбиений. Аналогично, он хочет знать, может ли он являтся сноской в каком-нибудь из корректных разбиений. Помогите ему!

В первой и единственной строке задан текст книги, который содержит не более $10^6$ символов. Текст может состоять из строчных и заглавных латинских букв, цифр, символов ^, а также точек, запятых, вопросительных знаков, пробелов и двоеточий. Гарантируется, что в тексте после каждого символа ^ следует натуральное число (возможно, довольно большое). После каждого такого числа следует либо пробел, либо знак препинания (точка, запятая, двоеточие или вопросительный знак).

В первой строке выведите количество символов ^ в тексте. Во второй строке для каждого сивола ^ выведите Y, если он может являтся степенью, и N в противном случае. Аналогично в третьей строчке для каждого символа ^ выведите Y, если он может являтся сноской и N в противном случае.

Обратите внимание на то, что символы, стоящие перед ^, никак не влияют на то, может ли этот символ являться сноской или возведением в степень.