КОНДУКТОР

Нэгэн хотын хүн амын P%-аас эрс их бөгөөд Q%-аас эрс бага хувь нь кондукторууд байдаг бол уг хотын хүн ам хамгийн багадаа хэд байх ёстой вэ? 0.01 ≤ P, Q ≤ 99.99.

Том тооны дөрвөн үйлдэл энэ үйлдлүүд кодер дээр байгаа хичээлийг бодвол маш энгийн байх шиг санагдсан.

Бодлогын эх өгүүлбэр

Алхам Тоон шулуун дээр хоёр цэг өгөгджээ. Нэг цэгээс нөгөө цэг хүртэл Робот натурал тоон хэмжээтэй алхамаар алхана. Робот алхахдаа өмнөх алхамаас нэгээр илүү, нэгээр бага, эсвэл өмнөхтэй ижил хэмжээтэй мөн эхний алхам ба сүүлийн алхамд заавал 1 хэмжээтэй алхана. Тэгвэл өгөгдсөн цэгээс өгөгдсөн цэг хүртэл Робот хамгийн цөөн алхаж хүрэх алхамын тоог олох програм бич.

Оролт:

Эхний цэгийн координат сүүлийн цэгийн координат нэг хоосон зайгаар тусгаарлагдан өгөгдөнө.0<=x,y<2⁶³

Гаралт: Роботын хамгийн цөөн алхаж хүрэх алхамын тоо байрлана.

Жишээ оролт 1:

45 48

Жишээ гаралт 1:

3

Жишээ оролт 2:

45 50

Жишээ гаралт 2:

4

Эх бодлого
Танд тэмдэгт мөр өгөгдөнө. Тэгвэл та N ширхэг үйлдэл (хувиргалт)-г тэкст дээр хийж, хувиргалт хийсний дараа үүссэн тэмдэгт мөрийг хэвлэж харуулна уу. Таны хийх үйлдлүүд нь :
L – курсорыг зүүн тийш нэг тэмдэг нүүлгэнэ. ( хэрвээ курсор тэмдэгт мөрийн хамгийн урд байрлаж байвал мэдээж курсор хөдлөхгүй. )
D – курсорыг баруун тийш нь нэг тэмдэг нүүлгэнэ. ( мөн курсор тэмдэгт мөрийн хамгийн хойно байрлаж байвал курсор хөдлөхгүй. )
B – курсорын зүүн талд байгаа нэг тэмдэгтийг усгана. ( курсор тэмдэгт мөрийн хамгийн урд байрлаж байвал үйлдэл хийгдэхгүй )
P # - # тэмдэгтийг курсорын зүүн талд тэмдэгт мөр дээр нэмнэ. ( # нь ямар нэгэн үсэг байна. )
Үйлдлүүд хийгдэхээс өмнө курсор тэмдэгт мөрийн хамгийн төгсгөлд буюу баруун захад байрлана.
Таны даалгавар бол өгөгдсөн тэмдэгт мөрт өгөгдсөн үйлдлүүдийг хийхэд шинээр үүсэх тэмдэгт мөрийг хэвлэж харуулах юм.
Оролт:
Эхний мөрөнд анхны тэмдэгт мөр өгөгдөх ба энэ нь жижиг латин үсэгнүүдээс бүрдэх ба 100000-аас ихгүй урттай байна.
Дараагийн мөрөнд хийгдэх үйлдлүүдийн тоо N (1<=N<=500000) өгөгдөнө.
Дараагийн N ширхэг мөрөнд таны хийх үйлдлүүд өгөгдөнө. Үйлдлүүдийг өгөгдсөн дараалалаар хийх ёстой юм.
Гаралт:
Бодлогын хариуг хэвлэ.
Жишээ.
Оролт:
abcd
11
B
B
P x
L
B
B
B
P y
D
D
P z
Гаралт:
yxz
Оролт:
abcdmln
13
L
B
L
P e
P r
L
L
L
P o
L
L
B
B
Гаралт:
codermn
Оролт:
a
3
P c
L
B
Гаралт:
c

   Эх бодлогын URL

Билет 0..9 цифрүүдээс бүрдсэн байдаг (Билет 0-р эхэлсэн байж болно). Азтай билет нь сондгой тооны хуваагчтай билет юм. Тэгвэл өгөгдсөн билетийг ямар нэгэн азтай билет болгоход шаардагдах хамгийн цөөн үйлдлийг тоог ол. Үйлдэл гэдэг нь билетийн ямар нэгэн цифрийг өөр цифрээр солихийг хэлнэ. Мөн дан 0 цифрээс бүтэх билетийг азтай билет гэж үз.

Оролт:

Оролтонд 3 билетийг тус бүрт нь нэг мөрөнд өгнө. Билетийн дугаарыг илэрхийлэх цифрүүдийн дараалал өгөгднө. Урт нь 10-аас хэтрэхгүй.

Гаралт:

Өгөгдсөн билетийг азтай билет болгоход шаардагдах хамгийн цөөн үйлдлийн тоо.

Жишээ оролт:

125

012

3127

Жишээ гаралт:

1

1

2

Тайлбар :

125 -> 121 121 нь 1, 11, 121 гэсэн 3 хуваагчтай.

012 -> 016 016 билетийг 16 гэж үзэх ба 16 нь 1, 2, 4, 8, 16 гэсэн 5 хуваагчтай.

  N тоо өгөгдөхөд доорх байдлаар хүснэгтийг N² хүртлэх тоогоор дүүргэе. Доорх жишээнд N=4 байгаа юм. Баавгай 1 гэсэн тоон дээр байрлах тухайн нүднээс дээшээ, доошоо, баруун тал, зүүн талын нүднүүдэд шилжиж чадах ба К удаа аль нэг нүднүүдрүү шилжив. Баавгай очсон нүд болгон дээр байгаа тоотой ижил загас иддэг. Танд N (1 <= N <= 100 000) болон баавгайн хийсэн алхамын тоо K (1 <= K <= 300 000) мэдээлэлтэйгээ өгөгдсөн бол баавгай нийт хэдэн загас идсэн бэ?

Оролт: эхний мөрөнд N K тоо дараагийн мөрөнд баавгайн дээшээ 'U', доошоо 'D', зүүн 'L', баруун 'R' аль зүгрүү алхасныг тодорхойлох К урттай тэмдэгт мөр.
Гаралт:
Баавгайн нийт идсэн загасны тоо.
Жишээ:
Оролт:
4 6
DDDRRR
Гаралт:
60
Оролт:
4 5
DRULD
Гаралт:
15

6030. Оройд харгалзах тоонууд

Бодлогын дугаар: RGB8063 spoj.pl/RGB8

Гогцоогүй ба ирмэг давхцаагүй чиглэлгүй граф дахь оройнуудад орой болон тухайн оройтой холбогдсон оройнуудын дугааруудын ерөнхий хуваагдагчийг утга болгон олгов.

Input

Эхний мөрөнд графын оройн тоо N өгөгдөнө. ( 0<N<7 )

Дараагийн мөрүүдэд холболтын матриц өгөгдөнө.

Output

Оройнуудад харгалзах N тоо.

Example

Input:
3

0 1 1

1 0 0

1 0 0

Output:
6 2 3