PIIMA

Xotira 32 MB Vaqt 1000 ms

14

Bir o'lchovli labirint

Dilshod xonalari $1$ dan $n$ gacha raqamlangan bir o'lchovli labirintda adashib qoldi. Hozirda u labirintning $k$ -xonasida turibdi va labirindan chiqish uchun $1$ -yoki $n$ -xonalardan biriga borishi kerak . Dilshod o'z istagi bilan yura olmaydi, shuning uchun ham turgan xonasining belgisilga qarab yuradi.

$L$ belgili xonada turgan bo'lsa hozirgi turgan xonasidan qo'shni chap xonaga o'ta oladi.
$R$ belgili xonada turgan bo'lsa hozirgi turgan xonasidan qo'shni o'ng xonaga o'ta oladi.

Harakat qilishni boshlashdan oldin, Dilshod istalgan xonalarining belgilarini almashtira oladi. U minimal nechta almashtirishlar yordamida labirintdan chiqib keta oladi?

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son - $T$ testlar soni kiritiladi.

Keyingi qatordan boshlab har bir test uchun alohida, birinchi qatorda $n(1 \leq n \leq 2 * 10^5)$ labirintdagi xonalar soni va $k(1 < k < n)$ hozirda Dilshod turgan xonaning tartib raqami kiritiladi. Ikkinchi qatorda esa bitta satr, labirintdagi xonalarning belgilar kiritiladi.

Barcha testlar kesimida $n$ larning yig'indisi $10^6$ dan oshmaydi.

Chiquvchi ma'lumotlar:

Har bir test uchun alohida qatorda, DIlshod minimal nechta o'zgartirishlar yordamida labirintdan chiqib ketishini toping.

Misollar

#	input.txt	output.txt
1	3 6 3 RLRRLR 4 2 LLRR 8 4 LRLRRLLL	1 0 2

Izoh:

1-testda, Dilshod labirintning 3-xonasid turibdi. 1 ta belgini o'zgartirish yordamida labirintni RLLRLR ko'rinishiga olib keladi.

So'ng quyidagicha harakat qiladi: RLLRLR → RLLRLR → RLLRL

1-raqamli xonaga kelib bo'lgach, Labirintdan chiqib ketadi.

2-testda faqat chapga yurgan holda labirintdan chiqib ketadi.

3-testda esa Dilshod oldin satrni LRLRRRRL ga o'zgartiradi.

So'ng quyidagicha harakat qiladi: LRLRRRRL → LRLRRRRL → LRLRRRRL → LRLRRRRL → LRLRRRRL. Oxirgi xonaga kelgach, labirintdan chiqib ketadi.

Masala F

Bir o'lchovli labirint