Divided Fractals

Ένα fractal είναι ένα γεωμετρικό αντικείμενο με την ιδιότητα ότι τα υποτμήματα του αντικειμένου φαίνονται πανομοιότυπα με (αλλά μικρότερα από) ολόκληρο το αντικείμενο. Εδώ εξετάζουμε ένα συγκεκριμένο fractal, το οποίο θα προσεγγίσουμε επαναλαμβάνοντας μια διαδικασία κατασκευής.

Ξεκινήστε με ένα γεμάτο τετράγωνο του οποίου το μήκος πλευράς είναι ~1~. Για παράδειγμα:

* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *

Αφαιρέστε ένα τετράγωνο της πλευράς ~1/3~ από τη μέση:

* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * *                   * * * * * * * * *
* * * * * * * * *                   * * * * * * * * *
* * * * * * * * *                   * * * * * * * * *
* * * * * * * * *                   * * * * * * * * *
* * * * * * * * *                   * * * * * * * * *
* * * * * * * * *                   * * * * * * * * *
* * * * * * * * *                   * * * * * * * * *
* * * * * * * * *                   * * * * * * * * *
* * * * * * * * *                   * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *

Σημειώστε ότι αυτός ο αριθμός ισοδυναμεί με ~8~ τετράγωνα μεγέθους ~1/3~, όπως φαίνεται παρακάτω. Τα κενά μεταξύ των τετραγώνων είναι μόνο για απεικόνιση και δεν εμφανίζονται στο fractal.*

* * * * * * * * *   * * * * * * * * *   * * * * * * * * *
* * * * * * * * *   * * * * * * * * *   * * * * * * * * *
* * * * * * * * *   * * * * * * * * *   * * * * * * * * *
* * * * * * * * *   * * * * * * * * *   * * * * * * * * *
* * * * * * * * *   * * * * * * * * *   * * * * * * * * *
* * * * * * * * *   * * * * * * * * *   * * * * * * * * *
* * * * * * * * *   * * * * * * * * *   * * * * * * * * *
* * * * * * * * *   * * * * * * * * *   * * * * * * * * *
* * * * * * * * *   * * * * * * * * *   * * * * * * * * *

* * * * * * * * *                       * * * * * * * * *
* * * * * * * * *                       * * * * * * * * *
* * * * * * * * *                       * * * * * * * * *
* * * * * * * * *                       * * * * * * * * *
* * * * * * * * *                       * * * * * * * * *
* * * * * * * * *                       * * * * * * * * *
* * * * * * * * *                       * * * * * * * * *
* * * * * * * * *                       * * * * * * * * *
* * * * * * * * *                       * * * * * * * * *

* * * * * * * * *   * * * * * * * * *   * * * * * * * * *
* * * * * * * * *   * * * * * * * * *   * * * * * * * * *
* * * * * * * * *   * * * * * * * * *   * * * * * * * * *
* * * * * * * * *   * * * * * * * * *   * * * * * * * * *
* * * * * * * * *   * * * * * * * * *   * * * * * * * * *
* * * * * * * * *   * * * * * * * * *   * * * * * * * * *
* * * * * * * * *   * * * * * * * * *   * * * * * * * * *
* * * * * * * * *   * * * * * * * * *   * * * * * * * * *
* * * * * * * * *   * * * * * * * * *   * * * * * * * * *

Μπορούμε να εφαρμόσουμε αυτή τη διαδικασία ξανά σε καθένα από τα τετράγωνα. Έτσι, μετά από ~2~ επαναλήψεις της διαδικασίας κατασκευής, έχουμε:

* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * *       * * * * * *       * * * * * *       * * *
* * *       * * * * * *       * * * * * *       * * *
* * *       * * * * * *       * * * * * *       * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * *                   * * * * * * * * *
* * * * * * * * *                   * * * * * * * * *
* * * * * * * * *                   * * * * * * * * *
* * *       * * *                   * * *       * * *
* * *       * * *                   * * *       * * *
* * *       * * *                   * * *       * * *
* * * * * * * * *                   * * * * * * * * *
* * * * * * * * *                   * * * * * * * * *
* * * * * * * * *                   * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * *       * * * * * *       * * * * * *       * * *
* * *       * * * * * *       * * * * * *       * * *
* * *       * * * * * *       * * * * * *       * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *

Κάθε ένα από τα οκτώ τετράγωνα είναι πλέον αντίγραφο της πρώτης επανάληψης. Κάθε ένα από αυτά περιέχει οκτώ γεμάτα τετράγωνα, για ένα σύνολο ~64~. Η διαδικασία εφαρμόζεται σε καθένα από αυτά τα τετράγωνα. Μετά από ~3~ επαναλήψεις έχουμε:

* * * * * * * * * * * * * * * * * * * * * * * * * * *
*   * *   * *   * *   * *   * *   * *   * *   * *   *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * *       * * * * * *       * * * * * *       * * *
*   *       *   * *   *       *   * *   *       *   *
* * *       * * * * * *       * * * * * *       * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
*   * *   * *   * *   * *   * *   * *   * *   * *   *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * *                   * * * * * * * * *
*   * *   * *   *                   *   * *   * *   *
* * * * * * * * *                   * * * * * * * * *
* * *       * * *                   * * *       * * *
*   *       *   *                   *   *       *   *
* * *       * * *                   * * *       * * *
* * * * * * * * *                   * * * * * * * * *
*   * *   * *   *                   *   * *   * *   *
* * * * * * * * *                   * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
*   * *   * *   * *   * *   * *   * *   * *   * *   *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * *       * * * * * *       * * * * * *       * * *
*   *       *   * *   *       *   * *   *       *   *
* * *       * * * * * *       * * * * * *       * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
*   * *   * *   * *   * *   * *   * *   * *   * *   *
* * * * * * * * * * * * * * * * * * * * * * * * * * *

Το πραγματικό fractal είναι αυτό που παίρνουμε όταν αυτή η διαδικασία επαναλαμβάνεται άπειρες φορές. Όπως θα περίμενε κανείς, καθένα από τα ~8~ υποτμήματα αυτού του fractal είναι ένα ακριβές αντίγραφο του fractal, κλιμακούμενο με συντελεστή ~1/3~.

1. Εάν η διαδικασία επαναληφθεί ~n~ φορές ~(n \ge 1)~ , πόσες τρύπες υπάρχουν στο τετράγωνο;

1. Μετά από ~n~ επαναλήψεις, ποια είναι η συνολική γεμισμένη επιφάνεια;
2. Μετά από άπειρο αριθμό επαναλήψεων, ποια είναι η συνολική γεμισμένη επιφάνεια;
3. Γράψτε ένα πρόγραμμα για τον υπολογισμό της καθορισμένης συνάρτησης μετά από ~n~ επαναλήψεις ~(n \le 5)~. Για να το κάνετε αυτό, αντιπροσωπεύστε το σχήμα ως πλέγμα ~3^n~ επί ~3^n~, με το '' να υποδεικνύει τις γεμάτες περιοχές και το ' ' να υποδεικνύει τις μη συμπληρωμένες περιοχές. Το σχήμα θα είναι πολύ μεγάλο για να εκτυπωθεί σε μία οθόνη ή φύλλο χαρτιού, επομένως η είσοδος θα καθορίσει ένα μικρό ορθογώνιο τμήμα της εικόνας που θα εκτυπωθεί.
   
   Η πρώτη γραμμή εισόδου περιέχει έναν θετικό ακέραιο ~d~, που υποδεικνύει τον αριθμό των δεδομένων δοκιμής που θα ακολουθήσουν. Κάθε σύνολο δεδομένων δοκιμής αποτελείται από πέντε γραμμές που περιέχουν:
   
   ~n~, ο αριθμός των επαναλήψεων ~(0 \le n \le 5)~
   ~b~, την κάτω σειρά του προς εκτύπωση ορθογωνίου ~(1 \le b \le 3^n)~
   ~t~, την επάνω σειρά του προς εκτύπωση ορθογωνίου ~(b \le t \le 3^n)~
   ~l~, η αριστερή στήλη του προς εκτύπωση ορθογωνίου ~(1 \le l \le 3^n)~
   ~r~, η δεξιά στήλη του προς εκτύπωση ορθογωνίου ~(l \le r \le 3^n)~
   
   Σημειώστε ότι οι σειρές αριθμούνται από κάτω προς τα πάνω και οι στήλες από αριστερά προς τα δεξιά.
   
   Υπολογίστε το σχήμα και εκτυπώστε το καθορισμένο ορθογώνιο τμήμα, με μία γραμμή εξόδου ανά σειρά. Εκτυπώστε πρώτα την επάνω σειρά και τελευταία την κάτω σειρά. Για να κάνετε την έξοδο να φαίνεται τετράγωνη, αφήστε ένα ενιαίο οριζόντιο κενό μεταξύ των στοιχείων της σειράς (όπως γίνεται στα παραπάνω παραδείγματα). Αφήστε μια κενή γραμμή στην έξοδο μετά από κάθε δοκιμαστική περίπτωση.

Παράδειγμα

input

1
3
2
10
5
27

output

* * * * *                   * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * *
  * *   * *   * *   * *   * *   * *   * *   *
* * * * * * * * * * * * * * * * * * * * * * *
    * * * * * *       * * * * * *       * * *
    *   * *   *       *   * *   *       *   *
    * * * * * *       * * * * * *       * * *
* * * * * * * * * * * * * * * * * * * * * * *
  * *   * *   * *   * *   * *   * *   * *   *