A. Удирдлагын штаб

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Хоёр хэмжээст ертөнцөд сэнсац дэгдэв! Цагдаа нар маш аюултай "Pihters" бүлгийн гишүүн өндөр аюултай хүнийг баривчилжээ. Хуулийн байгуулгын мэдээлснээр хууль зөрчигч нь бүлгийн удирдлагын штабаас жолоодож яваад зайрмагны мухлагруу мөргөжээ. Хоёр хэмжээст ертөнцөд зайрмагний мухлаг, удирдлагын штаб, машин бүгд нэг цэгийг эзлэнэ.

Хууль зөрчигчийн машин GPS төхөөрөмжтэй. Машин удирдлагын штабаас мухлаг хүртэл яг $n$ нүүдэл явсан байсныг төхөөрөмж харуулсан. Нүүдэл нь машиныг (x, y) цэгээс яг дөрвөн тийш хөдөлгөж чадна: L-ээр $(x - 1, y)$, R-аар $(x + 1, y)$, D-ээр $(x, y - 1)$, U-аар $(x, y + 1)$ цэгүүдрүү очих хөдөлгөөнийг дүрсэлсэн.

GPS төхөөрөмж нь нарын ажилгдаггүй бөгөөд машин хөдөлгөөний жинхэнэ дарааллыг хадгалж чадахгүй. Оронд нь төхөөрөмж машины боломжтой нүүдлүүдийн талаарх тэмдэглэлийг хадгалдаг. Тэмдэглэл бүр тэмдэгтэн цуваа ба утга нь "UL", "UR", "DL", "DR", "ULDR" эдгээрийн аль нэг байна. Ийм тэмдэгтэн цуваа болгон машин тэмдэгтэн цуваанд байгаа үсгүүдийн аль нэг үйлдлийг хийсэн гэсэн үг. Жишээ нь "UL" гэвэл машин "U" эсвэл "L" зүгт явсан гэсэн үг.

Хууль зөрчигчийн удирдлагын штабаас мухлаг хүртэлх боломжит нүүдлүүдийн тэмдэглэл танд өгөдсөн. Тэмдэглэл цаг хугацааны дараалалтайгаар тэмдэглэгдсэн. Зайрмагны мухлаг $(0, 0)$ цэг дээр байгаа гэдэг нь өгөгдсөн бол та дээрэмчдийн удирдлагын штаб байж болох хэдэн өөр цэг байгааг ол (машины эхлэлийн цэг).

Оролт

Эхний мөр удирдлагын штабаас мухлаг хүртэлх нүүдлийн тоог заах ганц бүхэл тоо $n (1 <= n <= 2*10^5)$-ийг агуулна.

Доорх $n$ мөр бүр машины боломжит нүүдлүүдийг дүрслэнэ. Боломжит нүүдэл болгон доорх тэмдэгтэн цуваануудын аль нэг нь болох нь баталгаатай: "UL", "UR", "DL", "DR", "ULDR".

Бүх нүүдлүүд цаг хугацааны дарааллаар өгөгдсөн.

C++ дээр 64-bit бүхэл тоог уншихдаа бүү %lld хэрэглэ. cin, cout урсгал эсвэл %I64d хэрэглэ.

Гаралт

Тээрэмчдийн удирдлагын штаб байж болох өөр өөр байрлалыг заах ганц бүхэл тоог хэвлэнэ.

Орчуулсан: devman

Жишээ тэстүүд

Оролт
3
UR
UL
ULDR
Гаралт
9
Оролт
2
DR
DL
Гаралт
4

Тэмдэглэл

Эхний жишээнд дээрэмчдийн удирдлагын штаб байж болох 9 өөр цэгүүдийг харуулав.

% zurag

Жишээ нь доорх нүүдлүүд машинийг (1, 0) цэгээс (0, 0) цэгрүү авчирж чадна.

Сэтгэгдлүүдийг ачааллаж байна...