Papírhajtogatás

Amikor egy papírdarabot bele szeretnénk tenni egy borítékba, gyakran össze kell azt hajtanunk egyszer vagy többször, hogy beleférjen. A hajtogatás módjától függően a papír eredeti nézetének különböző részei lesznek láthatók a hajtogatás után. A feladatod, hogy írj egy programot, amely 1) kiszámítja, hogy a papír melyik része lesz látható hajtogatások egy adott sorozata után, illetve 2) kiszámítja, hogyan kell hajtogatni egy papírt ahhoz, hogy egy adott része legyen látható.

8 különböző módon lehet kettéhajtani egy darab papírt, ha meg szeretnénk felezni a méretét. Ezek a következők:

• a papír bal felének hajtása a jobb fele fölé („l”, mint „left”)
• a papír jobb felének hajtása a bal fele fölé („r”, mint „right”)
• a papír felső felének hajtása az alsó fele fölé („t”, mint „top”)
• a papír alsó felének hajtása a felső fele fölé („b”, mint „bottom”)
• a papír bal felének hajtása a jobb fele alá („L”)
• a papír jobb felének hajtása a bal fele alá („R”)
• a papír felső felének hajtása az alsó fele alá („T”)
• a papír alsó felének hajtása a felső fele alá („B”)

Ebben a feladatban a papír mérete 1048576 × 1048576 egység (merő véletlenségből ez azt jelenti, hogy a papír oldalainak hossza legfeljebb 20 hajtás után mindig egész szám lesz). A papír bal felső sarkának a koordinátái (0,0), a jobb alsó sarkáé pedig (1048576,1048576). Ez igaz mind a papír elülső oldalára, mind a hátulsóra. Tehát ha (valamilyen okból) vízszintesen megfordítanád a papírt, akkor a (0,0) koordináta a jobb felső sarokba kerülne.

Ha például az első hajtásod egy „t”, akkor a papír felső felét hajtjuk, így a papír hátuljának a felső fele kerül előre. A látható rész (azaz az elülső rész) tehát a (0,0) – (1048576,524288) terület lesz az eredeti nézet hátuljából.

Feltételezheted, hogy a hajtások borotvaélesek. A valóságban szinte lehetetlen lenne egy papírdarabot 20-szor félbehajtani.

A bemenet specifikációja

A bemenet első sora egyetlen n egész számot, a tesztesetek számát tartalmazza.

Ezt n sor követi, amelyek mindegyike vagy 1) egy hajtássorozatot, vagy 2) egy kívánt látható részt ír le. A hajtássorozat egy legalább 1, legfeljebb 20 karaktert tartalmazó sztringként lesz megadva, amelynek minden karaktere a fent ismertetett, hajtogatást leíró karakterek egyike („l”, „r”, „t”, „b”, „L”, „R”, „T”, „B”). A látható rész (x1,y1)–(x2,y2) S formában lesz megadva, ahol (x1,y1) és (x2,y2) a kívánt rész sarkainak koordinátái (x1 < x2, y1 < y2), S pedig vagy F (mint „front side”; ha az eredeti nézet elülső oldalát szeretnénk), vagy B (mint „back side”; ha a hátulsó oldalt szeretnénk).

A kimenet specifikációja

Minden bemeneti sorra egyetlen sort kell a kimenetre írni pontosan a bemenet formátumában (csak az ellenkező esetre!). A részletekért lásd a példa kimenetet!

Ha egynél több hajtássorozat is létezik a kívánt rész eléréséhez (felteheted, hogy legalább egy mindig létezik), akkor közülük a lexikografikusan legkisebbet kell kiírni. Más szóval a hajtások preferencia-sorrendje a következő: „B”, „L”, „R”, „T”, „b”, „l”, „r”, „t”.

Példa bemenet

1. 6
2. l
3. (0,0)-(524288,1048576) B
4. rLbb
5. (786432,262144)-(1048576,524288) B
6. BBtttTLbLRrLb
7. (98304,319488)-(131072,323584) F

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. (0,0)-(524288,1048576) B
2. l
3. (786432,262144)-(1048576,524288) B
4. bbLL
5. (98304,319488)-(131072,323584) F
6. BBbBBbbbLlllL

letöltés szöveges állományként