Краплі на таці

Є прямокутна таця, яка складається з $h$ рядків та $w$ стовпців клітинок. Під час реалізації мовою C++ додайте директиву #define lll long long та використовуйте lll для 64-бітних цілих чисел. Під час реалізації мовою Python додайте на початку програми рядок lll = int та перетворюйте на число кожне прочитане значення викликом lll(...). Спочатку в кожній клітинці є рівно одна крапля води.

На всі краплі можна одночасно застосовувати такі команди:

• L — пересунути кожну краплю на одну клітинку ліворуч;

• R — пересунути кожну краплю на одну клітинку праворуч;

• U — пересунути кожну краплю на одну клітинку вгору;

• D — пересунути кожну краплю на одну клітинку вниз.

Якщо крапля мала б вийти за межі таці, вона залишається на місці. Якщо після виконання команди кілька крапель опиняються в одній клітинці, вони зливаються в одну краплю. Надалі вона рухається за тими самими правилами й не може розділитися.

Вам дано рядок $s$ довжини $m$, що складається з команд. Ви можете вибрати будь-який непорожній послідовний фрагмент цього рядка з позиції $l$ до позиції $r$ включно (1 \le l \le r \le m) і виконати лише команди з цього фрагмента в заданому порядку. Перед виконанням вибраного фрагмента в кожній клітинці таці є рівно одна крапля.

Знайдіть найменшу довжину фрагмента, після виконання якого всі краплі опиняться в одній клітинці. Якщо такого фрагмента не існує, виведіть $-1$.

Приклад для h = 2, w = 3 та s = \texttt{LRRU}