Агенцијата за млади и спорт на Република Македонија започнува нова кампања „Со здраво тело до здрава фамилија“ во која ги поттикнува сите семејства на спорт. Со цел да го распространат спортот во семејствата тие направиле план за промоција на нивната кампања. Бидејќи агенцијата располага со регистар на семејства кои спортуваат (т.н. спортски семејства) тие решиле преку нив да направаат промоција на спортот со цел семејствата кои не се занимаваат со спорт (т.н. неспортски семејства) да почнат час поскоро да спортуваат.

По должината на една улица од едната и од другата страна се сместени 2N спортски и неспортски семејства (N семејства од едната и N семејства од другата страна на улицата). Секое семејство има точно 3 соседни семејства: лево од нив, десно од нив и семејството од спротивната страна на улицата (освен оние семејства на почеток и на крај на улицата, кои имаат по две соседни семејства).

Секое од спортските семејства е означено со S, секое неспортско семејство е означено со P. Секогаш кога семејство А ќе отиде на гости кај семејството Б успева да го убеди семејството Б да го смени своето спортско убедување во она кое го има семејството А. Пример, ако А е S семејство и разговара со Б кое е P семејство, по разговорот Б станува S. Спортското убедување на А не се менува кога тоа оди да разговара со Б. Значи, во претходниот пример А останува Ѕ семејство.

Планот на агенцијата е преку спортските семејства да се активираат неспортските и за тоа постојат три различни операции преку кои семејствата може да разговараат и притоа да го сменат своето спортско убедување. Тие се:

1. Да се избере семејство А. Да се избере едно од соседните семејства на А - нека е тоа Б. А разговара со Б.

2. Да се избере група од последователни семејства на иста страна на улицата. Секое од овие семејства разговара со семејството од спротивната страна на улицата.

3. Да се изберат две соседни семејства (на спротивни страни од улицата). Нека се тоа семејствата А1 и А2. Да се изберат други две семејства (Б1 и Б2) кои се едно наспроти друго преку улицата и соседни со А1 и А2 соодветно. А1 разговара со Б1, а А2 разговара со Б2.

Ако е дадена состојбата на семејствата по должината на една улица вратете го најмалиот ненегативен цел број Х така што постои редослед на Х последователни операции по чие извршување сите семејства ќе спортуваат. Ако не постои таков редослед на операции се враќа -1.

Влез

Во првата линија се испишани N знаци (S или P) кои го опишуваат спортското убедување на секое од семејствата од едната страна на улицата, редоследно. Во втората линија се напишани N знаци кои го опишуваат спортското убедување на семејствата од другата страна на улицата, редоследно. (1 ≤ N ≤ 200)

Излез

Во една линија се печати еден ненегативен цел број кој го претставува бројот на операции кои треба редоследно да се извршат за сите семејства да станат спортски, ако е тоа можно. Во спротивно се печати -1.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
SPS
PSP

излез
2

влез
SS
SS

излез
0

влез
P
P

излез
-1

Објаснување за првиот тест пример: Второто семејство од втората линија разговара со второто семејство од првата линија (операција 1). Потоа сите семејства од првата линија разговараат со семејствата од втората линија (операција 2).

Друг начин: Ако прво ја примениме операцијата 2, сите семејства од првиот ред разговараат со оние од вториот. Спортското убедување на семејствата од вториот ред ќе биде SPS. Потоа ја применуваме операцијата 3, првите семејства од двата реда разговараат со вторите семејства од двата реда.