Polling Stations

Η εκλογική περίοδος πλησιάζει στο Κίτσενερ! Αφού αποσύρθηκε από τα καθήκοντά της ως δήμαρχος, φέτος η Alanna υπηρετεί ως Επικεφαλής Εκλογικός Υπεύθυνος της πόλης. Όλα πήγαινουν καλά έως τώρα, αλλά υπάρχει ένα σημαντικό πρόβλημα - οι σταθμοί ψηφοφορίας ακόμη δεν διαθέτουν λογισμικό!

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

Ωστόσο, μην ξεγελαστείς από την απλότητα αυτής της εργασίας! Οι υπολογιστές στους σταθμούς ψηφοφορίας είναι αρχαίοι και μπορούν να προγραμματιστούν μόνο σε μια απαρχαιωμένη, δυσνόητη γλώσσα που ονομάζεται APL (Advanced Polling Language). Η APL υποστηρίζει μόνο δυαδικές μεταβλητές, καθώς και τις ~4~ δυαδικές πράξεις AND, OR, NOT και XOR (οι οποίες μπορούν να εφαρμοστούν σε αυτές τις μεταβλητές). Είσαι έτοιμος για την πρόκληση;

Πιο συγκεκριμένα, σου δίνονται οι περιορισμοί ~N~ και ~M~ και στόχος σου είναι να εκτυπώσεις ένα πρόγραμμα APL που διαβάζει έναν δυαδικό αριθμό ~x~ με ~N~ bit και έναν δυαδικό αριθμό ~y~ με ~M~ bit και εκτυπώνει το γινόμενό τους ~x \times y~ ως έναν δυαδικό αριθμό με ~(N + M)~ bit. Επιπλέον, επειδή οι υπολογιστές των σταθμών ψηφοφορίας είναι πολύ αργοί, το πρόγραμμά σου επιτρέπεται να περιέχει το πολύ ~C~ εντολές συνολικά.

Για την πλήρη περιγραφή της εξόδου, δες την παρακάτω ενότητα «Προδιαγραφές Εξόδου».

Σημείωση σχετικά με τη βαθμολόγηση: Το πρόγραμμα APL που θα εκτυπώσει ο κώδικάς σου θα αξιολογηθεί σε πολλαπλές περιπτώσεις ελέγχου. Κάθε περίπτωση ελέγχου θα προσομοιώνει με τη σειρά της την εκτέλεση του προγράμματός σου σε πολλαπλά ζεύγη εισόδων ~(x, y)~. Αν το πρόγραμμα APL δεν υπολογίζει σωστά το αποτέλεσμα για έστω και ένα ζεύγος εισόδων, θα θεωρηθεί λανθασμένο για τη συγκεκριμένη περίπτωση ελέγχου. Δυστυχώς, η εκλογική επιτροπή δεν διαθέτει τους απαραίτητους πόρους για να δοκιμάσει το πρόγραμμά σου σε έναν πραγματικό σταθμό ψηφοφορίας.

Είσοδος

Η πρώτη και μοναδική γραμμή της εισόδου θα περιέχει ~3~ ακέραιους αριθμούς, ~N~, ~M~ και ~C~.

Ο παρακάτω πίνακας δείχνει πώς κατανέμονται οι ~25~ διαθέσιμοι βαθμοί:

Βαθμοί	Περιορισμοί
~2~	~N = 2~, ~M = 1~, ~C = 2 \cdot 10^6~
~4~	~N \le 200~, ~M \le 2~, ~C = 2 \cdot 10^6~
~4~	~N \le 200~, ~M \le 6~, ~C = 2 \cdot 10^6~
~9~	~N \le 200~, ~M \le 200~, ~C = 2 \cdot 10^6~
3	~N \le 200~, ~M \le 200~, ~C = 500.000~
3	~N \le 200~, ~M \le 200~, ~C = 300.000~

Έξοδος

Εκτύπωσε ένα έγκυρο πρόγραμμα APL. Οι προδιαγραφές της γλώσσας APL είναι οι εξής:

Στην πρώτη γραμμή, εκτύπωσε έναν ακέραιο αριθμό ~c~ (~1 \le c \le C~), που αντιστοιχεί στον αριθμό των εντολών του προγράμματος.

Οι επόμενες ~c~ γραμμές πρέπει να περιέχουν από μία πύλη η καθεμία. Κάθε πύλη πρέπει να έχει μία από τις ακόλουθες ~4~ μορφές:

AND <in1> <in2>
OR <in1> <in2>
XOR <in1> <in2>
NOT <in1>

Οι παράμετροι <in1> και <in2> είναι αναγνωριστικά μεταβλητών που αντιστοιχούν στις εισόδους κάθε πύλης. Η APL υποστηρίζει μόνο δυαδικές μεταβλητές, καθεμία από τις οποίες αναγνωρίζεται από έναν ακέραιο αριθμό.

Επιπλέον, σημείωσε ότι οι εντολές του προγράμματός σου εκτελούνται με διαδοχική σειρά. Αυτό σημαίνει ότι οι παράμετροι <in1> και <in2> πρέπει να αναφέρονται σε μεταβλητές που έχουν ήδη δηλωθεί ως έξοδοι προηγούμενων εντολών. Ο τρόπος με τον οποίο ορίζονται και ερμηνεύονται οι μεταβλητές περιγράφεται παρακάτω.

Οι πρώτες ~N~ μεταβλητές (με αναγνωριστικά από ~0~ έως ~N - 1~) αντιστοιχούν στα bit του πρώτου αριθμού εισόδου ~x~, από το λιγότερο σημαντικό προς το περισσότερο σημαντικό bit. Οι επόμενες ~M~ μεταβλητές (με αναγνωριστικά από ~N~ έως ~N + M - 1~) αντιστοιχούν στα bit του δεύτερου αριθμού εισόδου ~y~, με την ίδια σειρά.

Στη συνέχεια, η έξοδος κάθε πύλης δημιουργεί μία νέα μεταβλητή, ξεκινώντας από τη μεταβλητή με αναγνωριστικό ~N + M~ (για παράδειγμα, η πρώτη πύλη παράγει τη μεταβλητή ~N + M~, η δεύτερη τη μεταβλητή ~N + M + 1~ κ.ο.κ.).

Τέλος, οι τελευταίες ~N + M~ μεταβλητές (οι οποίες είναι οι έξοδοι των τελευταίων ~N + M~ πυλών) θα ερμηνευθούν ως η δυαδική αναπαράσταση του γινομένου ~z~ (όπου ~z = x \times y~), με τη σειρά από το λιγότερο σημαντικό προς το περισσότερο σημαντικό bit. Κατά συνέπεια, αν το πρόγραμμά σου περιέχει λιγότερες από ~N + M~ πύλες, θα θεωρηθεί λανθασμένο.

Παράδειγμα

input

1 1 2000000

output

5
OR 0 1
NOT 2
AND 3 3
NOT 4
XOR 4 4

Επεξήγηση του παραδείγματος:

Το πρόγραμμα APL που εκτυπώνεται υπολογίζει το bitwise OR των αριθμών εισόδου ~x~ και ~y~ και αποθηκεύει το αποτέλεσμα στον αριθμό εξόδου ~z~. Σημείωσε ότι αυτό το πρόγραμμα υπολογίζει λανθασμένα το ~x \times y~ και παρατίθεται μόνο για σκοπούς επίδειξης.

Επιπλέον, σημείωσε ότι, καθώς οι αριθμοί ~x~ και ~y~ έχουν και οι δύο μήκος ~1~ bit, ο αριθμός εξόδου ~z~ αναμένεται να έχει μήκος ~1 + 1 = 2~ bit, συμπεριλαμβανομένων και τυχόν μηδενικών στην αρχή.