A. Oddiy masala

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Do'kon oynasiga faqat 'p', 'q' va 'w' belgilaridan tashkil topgan biror satr yozilgan. Samir ismli kishi do'kon oynasi oldidan o'tib ketayotganda, oyna tashqarisidan aaa satrni kuzatadi. Keyin u do'kon ichkarisiga kirib, oyna ichkarisidan qaraydi va bbb satrni kuzatadi.

Sizga aaa satri beriladi. Sizning vazifangiz bbb satrni topish va chiqish ma'lumotida chop etishdan iborat.

Kiruvchi ma'lumotlar:

Birinchi qatorda ttt \((1≤t≤100)\) — test holatlari soni beriladi.
Keyingi har bir qatorda faqat 'p', 'q', va 'w' belgilaridan tashkil topgan aaa satr keltiriladi (\(1 \leq |a| \leq 100)(1≤∣a∣≤100\)).

Chiquvchi ma'lumotlar:

Har bir test holati uchun alohida qatorda bbb satrni chop eting. Bu oynaning ichki tomonida kuzatilgan satr bo'ladi.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 qwq ppppp pppwwwqqq wqpqwpqwwqp pqpqpqpq	pwp qqqqq pppwwwqqq qpwwpqwpqpw pqpqpqpq

B. Minimal KOPRIM

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Bugun Kichik Samir barcha jamg'armasini bir segment sotib olishga sarfladi. U ushbu segmentda uy qurmoqchi.
Ijobiy sonlar segmenti [l,r] koprim deyiladi, agar l va r koprim bo'lsa.

Koprim segment [l,r] minimal koprim deb ataladi, agar u o'z ichiga o'zidan boshqa hech qanday koprim segmentni olmasa. Ushbu bayonotni yaxshiroq tushunish uchun izohlar qismiga murojaat qilishingiz mumkin.

Sizga ijobiy sonlar segmenti [l,r] berilgan. Ushbu segment ichida nechta minimal koprim segment borligini toping.

Kiruvchi ma'lumotlar:

Har bir testda bir nechta test holatlari mavjud.
Birinchi qatorda test holatlari soni t \((1 \leq t \leq 100)\) keltiriladi.

Keyingi qatorlarning har birida ikkita butun son l va r \((1≤l≤r≤109)\) beriladi.

Chiquvchi ma'lumotlar:

Har bir test holati uchun alohida qatorda [l,r] segment ichidagi minimal koprim segmentlar sonini chop eting.

Izoh:

Birinchi test holatida berilgan segment [1,2]. Ushbu segment ichida quyidagi segmentlar mavjud:

[1,1]: Bu koprim segment, chunki 1 va 1 koprim va segment ichida boshqa koprim segment yo'q. Demak, bu minimal koprim.
[1,2: Bu segment koprim, lekin u [1,1] ni o'z ichiga oladi. Shu sababli, bu minimal emas.
[2,2]: Bu segment koprim emas, chunki 2 va 2 1 va 2 musbat umumiy bo'luvchilarga ega.

Shunday qilib, segment [1,2] ichida faqat 1 ta minimal koprim segment mavjud.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	6 1 2 1 10 49 49 69 420 1 1 9982 44353	1 9 0 351 1 34371

C. Squide Game #Pechenie o‘yini

Xotira: 32 MB, Vaqt: 100 ms

Masala

Samir uzoq va sermazmun kunlardan keyin nihoyat katta mukofot mavjud bo‘lgan "Sqoude Game" tanloviga taklif qilindi. Bu tanlov ancha mashhur bo‘lib, minglab odamlar omad va mashaqqat bilan g‘alabaga erishishga harakat qiladilar. Mukofot juda katta bo‘lgani uchun Samir ham bu imkoniyatni qo‘ldan boy bermaslikka qaror qildi.

U mashaqqat bilan barcha shartlar da g'olib bo'lib vanihoyat “Pechenie o‘yini” ga yetib keldi.

O'yinning asosiy qoidasi quyidagicha: har bir qatnashchiga turli xil geometrik shakllardan iborat maxsus pechenielar beriladi. Har bir pecheniening o‘lchami va shakli oldindan belgilanadi. Tanlovning asosiy sharti — pechenieni shakl buzilmasdan kesib olishdir. Agar shakl noto‘g‘ri yoki buzilgan bo‘lsa, qatnashchi tanlovdan chetlatiladi (Die).

Pechenielar quyidagi shakllardan biri ko‘rinishida bo‘ladi:

"uchburchak" — asosiy tomoni keng, uchlari qiyinchilik tug‘diradigan shakl.
"kvadrat" — simmetrik va tartibli bo‘lsa-da, e'tiborli kesishni talab qiladi.
"aylana" — eng mashaqqatli shakllardan biri bo‘lib, Samir undan doimo ehtiyot bo‘ladi.

Samirga har safar pechenie shakli bilan birga uning kengligi va balandligi o‘lchamlari ham beriladi. Endi Samirning g‘olib bo‘lishi uchun ushbu shaklni to‘g‘ri aniqlab, chizib chiqishi muhim.

Siz dasturchi sifatida Samirga yordam berishingiz kerak. Kiritilgan ma’lumotlarga asoslanib, ushbu shaklni * (yulduzcha) belgisi yordamida chizishingiz lozim. Agar shakl nomi noto‘g‘ri bo‘lsa, Samirni ogohlantirib, "Noto'g'ri shakl!" degan xabarni chiqarishingiz kerak.

Kiruvchi ma'lumotlar:

Birinchi qator: ikki butun son W va H (1 ≤ W , H ≤ 50) — shaklning kengligi va balandligi.

Ikkinchi qator: shakl nomi ("uchburchak", "kvadrat", "aylana").

Chiquvchi ma'lumotlar:

Birinchi qatorda shakl nomi kichik lotin harflari bilan.

Ikkinchi qatorda agar shakl "uchburchak", "kvadrat" yoki "aylana" bo'lsa, ichki qismi bo'sh bo'lgan shaklni yulduzcha (*) belgisi bilan chizing.
Agar shakl nomi noto‘g‘ri bo‘lsa, ekranga "Noto'g'ri shakl!" deb chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 5 uchburchak	uchburchak * * * * * * * * * * * *
2	4 4 kvadrat	kvadrat * * * * * * * * * * * *
3	28 30 aylana	aylana ***** * * ** * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *******

#

INPUT.TXT

OUTPUT.TXT

1

5 5
uchburchak

uchburchak
    *
   * *
  *   *
 *     *
* * * * *

2

4 4  
kvadrat

kvadrat
* * * * 
*     * 
*     * 
* * * *

3

28 30
aylana

aylana
           *******           
        ***       ***        
      **             **      
     **               **     
    *                   *    
   *                     *   
  **                     **  
  *                       *  
 *                         * 
 *                         * 
 *                         * 
*                           *
*                           *
*                           *
*                           *
*                           *
*                           *
*                           *
 *                         * 
 *                         * 
 *                         * 
  *                       *  
  **                     **  
   *                     *   
    *                   *    
     **               **     
      **             **      
        ***       ***        
           *******