Банди

Центральна частина Внутрішнього Міста побудована у вигляді прямокутної сітки: вулиці пролягають з півночі на південь і мають номери від $1$-ої на заході до $20$-ої на сході, а проспекти проходять зі сходу на захід, починаючи з $1$-ого на півночі й до $20$-ого на півдні. Територію контролюють дві банди — Бліпси та Кради. Межа між їхніми районами — Зелена Лінія — проходить по діагоналі від перехрестя $1$-ої вулиці та $1$-ого проспекту до перехрестя $20$-ої вулиці й $20$-ого проспекту. Бліпси контролюють територію на південний захід від Зеленої Лінії, а Кради — територію на північний схід.

Щоб довести відвагу, Бліпси здійснюють "рейди" через район Крадів: стартують з $1$-ої вулиці та $1$-ого проспекту і завершують у точці на Зеленій Лінії, яка змінюється щоночі. Під час рейду не можна перетинати Зелену Лінію, але можна кілька разів повертатися до неї. Рух по проспектах можливий тільки на схід, а по вулицях лише на південь. Отже, рейд можна описати рядком із букв $E$ (схід) і $S$ (південь) довжини 2n - 2; кінець маршруту — на перехресті $n$-ої вулиці та $n$-ого проспекту.

Усі рейди однієї ночі (усі вони однакової довжини) Бліпси оцінюють за рівнем Оригінальної Гангстерськості (ОГ). Рейд R_1 вважається більш ОГ, ніж R_2, якщо:

• R_2 вперше повертається на Зелену Лінію раніше, ніж це робить R_1;

• R_1 і R_2 вперше повертаються на Зелену Лінію в одній і тій же точці, але частина шляху R_1 до цієї точки (ігноруючи початкову $E$ і фінальну $S$) є більш ОГ, ніж у R_2;

• R_1 і R_2 повертаються до Зеленої Лінії в одній точці і збігаються до цієї точки, але подальший маршрут R_1 є більш ОГ, ніж у R_2.

Приклади трьох вказаних випадків:

• EESS більш ОГ, ніж ESES.

• EEESSS більш ОГ, ніж EESESS.

• EESSEESS більш ОГ, ніж EESSESES.

Упорядкувавши всі рейди однієї довжини за рівнем ОГ, під рангом рейду розуміємо його позицію в цьому переліку. EESS має ранг $1$, ESES — ранг $2$.

Напишіть програму, що допоможе Бліпсам планувати та оцінювати нічні рейди.