28ος ΠΔΠ Γ' Φάση
Star Wars (starwars)

Η Αριάδνη πήγε για διακοπές στην Dinseyland στην Aμερική. Μια μέρα επισκέφτηκε το Star Tours που είναι αφιερωμένο στις κινηματογραφικές ταινίες Star Wars. Εκεί υπήρχε ένα ορθογώνιο παραλληλεπίπεδο με πλευρές \(X\)(μήκος) \(\times\) \(Y\)(πλάτος) \(\times\) \(Z\)(ύψος), αποτελούμενο από κύβους με πλευρά ίση με \(1\). Ας ονομάσουμε κάθε κύβο με τις τρεις συντεταγμένες του, ξεκινώντας την αρίθμηση σε κάθε διάσταση από το 0 (μηδέν) και πηγαίνοντας μέχρι \(X−1\), \(Y−1\) και \(Z−1\), αντίστοιχα. Κάθε κύβος είναι είτε φωτεινός είτε σκοτεινός. Ρίχνοντας μια δέσμη laser σε έναν κύβο, αυτός αλλάζει την κατάσταση του, από φωτεινός σε σκοτεινός και αντίστροφα. Στην αρχή, όλοι οι κύβοι είναι σκοτεινοί.

Η Αριάδνη βρήκε ένα όπλο ικανό να εκπέμπει «πλατιές» ακτίνες laser, που να χτυπούν συγχρόνως ολόκληρα επίπεδα με κύβους, σε οποιαδήποτε διάσταση \(X\), \(Y\) ή \(Z\). Χρησιμοποιώντας το, η Αριάδνη διαλέγει μια διάσταση (\(X\), \(Y\) ή \(Z\)) και δύο αριθμούς \(A\) και \(B\). Τότε, όλοι οι κύβοι που η συντεταγμένη τους στη συγκεκριμένη διάσταση είναι μεταξύ \(A\) και \(B\) (συμπεριλαμβανομένων) χτυπιούνται από το laser και αλλάζουν κατάσταση. Για παράδειγμα, αν επιλέξει τη διάσταση \(X\) και \(A=2\), \(B=3\), τότε όλοι οι κύβοι που η συντεταγμένη \(X\) τους είναι ίση με \(2\) ή \(3\) θα αλλάξουν κατάσταση.

Η Αριάδνη χρησιμοποιεί το όπλο πολλές φορές, για διάφορες διαστάσεις και διάφορες τιμές των \(A\) και \(B\). Θέλει όμως να ξέρει κάθε στιγμή πόσοι φωτεινοί κύβοι υπάρχουν σε οποιοδήποτε τμήμα του ορθογωνίου παραλληλεπιπέδου. Συγκεκριμένα, για κάθε ζεύγος συντεταγμένων \((x_1, y_1, z_1)\) και \((x_2, y_2, z_2)\) θέλει να ξέρει τον αριθμό των φωτεινών κύβων στο ορθογώνιο παραλληλεπίπεδο που έχει ως αντιδιαμετρικές κορυφές τους κύβους με αυτές τις συντεταγμένες.

Πρόβλημα

Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες της IOI (Pascal, C, C++, Java) το οποίο θα επεξεργάζεται τις βολές της Αριάδνης και ανά πάσα στιγμή θα απαντάει στις ερωτήσεις της.

Αρχεία Εισόδου

Το αρχείο εισόδου με όνομα starwars.in είναι αρχείο κειμένου που η πρώτη γραμμή του περιέχει έναν ακέραιο αριθμό \(N\), το πλήθος των δοκιμών που θα κάνει η Αριάδνη.

Για κάθε δοκιμή ακολουθεί ένα σύνολο γραμμών, η πρώτη από τις οποίες περιέχει τέσσερις ακέραιους αριθμούς \(X\), \(Y\), \(Z\), και \(M\), χωρισμένους ανά δύο με ένα κενό διάστημα. Οι πρώτοι τρεις είναι οι πλευρές του ορθογώνιου παραλληλεπίπεδου στις τρεις διαστάσεις. Το \(M\) είναι το πλήθος των πράξεων που θα ακολουθήσουν. Κάθε μία από τις επόμενες \(M\) γραμμές αντιστοιχεί σε μία πράξη. Οι πράξεις είναι της μορφής:

• \(0\) \(A\) \(B\): όλοι οι κύβοι με συντεταγμένη \(X\) από \(A\) μέχρι \(B\) (συμπεριλαμβανομένων) χτυπιούνται με laser (\(0 \le A \le B < X\)).
• \(1\) \(A\) \(B\): όλοι οι κύβοι με συντεταγμένη \(Y\) από \(A\) μέχρι \(B\) (συμπεριλαμβανομένων) χτυπιούνται με laser (\(0 \le A \le B < Y\)).
• \(2\) \(A\) \(B\): όλοι οι κύβοι με συντεταγμένη \(Z\) από \(A\) μέχρι \(B\) (συμπεριλαμβανομένων) χτυπιούνται με laser (\(0 \le A \le B < Z\)).
• \(3\) \(x_1\) \(y_1\) \(z_1\) \(x_2\) \(y_2\) \(z_2\): η Αριάδνη ρωτάει πόσοι φωτεινοί κύβοι υπάρχουν στο ορθογώνιο παραλληλεπίπεδο με αντιδιαμετρικές κορυφές τους κύβους \((x_1, y_1, z_1)\) και \((x_2, y_2, z_2)\). Θεωρήστε δεδομένο ότι \(0 \le x_1 \le x_2 < X\), ομοίως για τις άλλες διαστάσεις.

Προσέξτε ότι σε κάθε δοκιμή, η Αριάδνη ξεκινάει με ένα ορθογώνιο παραλληλεπίπεδο πιθανώς διαφορετικών διαστάσεων που όλοι του οι κύβοι είναι σκοτεινοί.

Αρχεία εξόδου

Το αρχείο εξόδου με όνομα starwars.out είναι αρχείο κειμένου αποτελούμενο από τόσες γραμμές όσες είναι οι ερωτήσεις στο αρχείο εισόδου. Κάθε γραμμή θα περιέχει έναν ακριβώς ακέραιο αριθμό, την απάντηση στην αντίστοιχη ερώτηση.

Παράδειγμα αρχείων εισόδου - εξόδου

starwars.in	starwars.out
2 2 2 2 5 0 0 0 1 1 1 3 0 0 0 1 1 1 2 1 1 3 0 0 0 0 1 1 4 5 6 6 0 2 2 0 2 3 1 3 3 3 0 0 0 2 3 3 2 0 3 3 1 1 1 2 2 2	4 2 12 8

Εξήγηση: (Για διευκόλυνσή σας, τα δεδομένα των δύο διαφορετικών δοκιμών εμφανίζονται χωρισμένα. Στα αρχεία εισόδου/εξόδου δε θα υπάρχουν κενές γραμμές.) Στην πρώτη δοκιμή, η κατάσταση των κύβων τη στιγμή των δύο ερωτήσεων φαίνεται στις παρακάτω εικόνες. Στην πρώτη ερώτηση η Αριάδνη ζητάει το πλήθος όλων των φωτεινών κύβων στην αριστερή εικόνα (\(4\)). Στη δεύτερη ερώτηση, ζητάει το πλήθος των φωτεινών κύβων με συντεταγμένη \(X=0\) στη δεξιά εικόνα (\(2\)).

Κατάσταση των κύβων στην πρώτη ερώτηση της πρώτης δοκιμής.

Κατάσταση των κύβων στη δεύτερη ερώτηση της πρώτης δοκιμής.

Όρια

Για το πλήθος των δοκιμών θα ισχύει \(1 \le N \le 15\).

• Για περιπτώσεις ελέγχου συνολικής αξίας 20%, θα είναι:
  \(1 \le X, Y, Z \le 100\)
  \(1 \le M \le 100\)
• Για περιπτώσεις ελέγχου συνολικής αξίας 60%, θα είναι:
  \(1 \le X, Y, Z \le 35000\)
  \(1 \le M \le 4000\)
• Για περιπτώσεις ελέγχου συνολικής αξίας 100%, θα είναι:
  \(1 \le X, Y, Z \le 10^5\)
  \(1 \le M \le 5000\)

Μέγιστος χρόνος εκτέλεσης: 1 sec
Μέγιστη διαθέσιμη μνήμη: 64 MB