• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

علی توانست شرکتش را توسعه دهد و یک زمین که به صورت یک جدول نامتناهی خریده و در هر خانه آن یک ترب کاشته است. همچنین یک دستگاه تربچین دارد که می‌خواهد با کمک آن ترب‌ها را برداشت کند...

علی از تربچه خواسته ابتدا تربچین را در قطعه $(0, 0)$ زمین قرار ‌دهد. تربچه برای آغاز کار یک رشته از حروف $\{L, R, U, D, ?\}$ دریافت می‌کند و طبق آن روی قطعه‌های زمین حرکت می‌کند و در هر قطعه که قرار بگیرد ترب داخل آن را می‌چیند.

همچنین اگر در یک خانه از جدول بیش از یک بار قرار بگیرد دیگر تربی برداشت نمی‌کند.

اگر رشته داده شده به تربچین $s_1s_2s_3...s_n\$ باشد. تربچین با توجه به این رشته $n$ حرکت انجام می‌دهد.اگر تربچین در خانه $(x, y)$ باشد بعد از انجام حرکت $i$ام :

• اگر $s_i=L$ باشد به خانه $(x-1, y)$
• اگر $s_i=R$ باشد به خانه $(x+1, y)$
• اگر $s_i=U$ باشد به خانه $(x, y+1)$
• اگر $s_i=D$ باشد به خانه $(x, y-1)$
• اگر $s_i=?$ باشد به یکی از چهار قطعه مجاور ضلعی

می‌رود.

علی رشته $s_1s_2s_3...s_n\$ را به ترب داده و او ترتیب عناصر این رشته را به هم ‌می‌ریزد. توجه کنید او نمی‌تواند حرفی به رشته اضافه یا کم کند!

علی که پیش‌بینی برایش خیلی مهم است؛ می‌خواهد بداند برای همه حالت‌های مختلف که ممکن است اتفاق بیفتد حداقل و حداکثر چند ترب توسط تربچین برداشت خواهد شد.

به علی کمک کنید تا این دو عدد را محاسبه کند.

ورودی🔗

در خط اول ورودی عدد $t$ داده می‌شود. در هر یک از $t$ سطر بعدی هر کدام یک رشته از حروف $\{L, R, U, D, ?\}$ داده می‌شود. تضمین می‌شود مجموع طول همه رشته‌ها از $100\ 000$ بیشتر نمی‌شود.

خروجی🔗

خروجی باید شامل $t$ سطر باشد که در سطر $i$ام دو عدد $a_i$ و $b_i$ چاپ می‌شود که نشان دهنده حداقل و حداکثر تعداد ترب‌های برداشت شده توسط تربچین است.

مثال🔗

ورودی نمونه ۱🔗

5
L
L?
UDU
????
LRURLDURDDD

خروجی نمونه ۱🔗

2 2
2 3
2 3
2 5
4 12

ترتیب‌های بیشینه و کمینه به ترتیب در هر مورد به صورت زیر است:

$L \to min = max = 2$

$LU \to max = 3, LR \to min = 2$

$UDU\to min = 2, UDU\to max = 3$

$LRLR \to min = 2, DDDD \to max = 5$

$RLRLRDUDUDD \to min = 4$

$LLUURRRDDDD \to max = 12$