Topovi

Ο Mirko είναι μεγάλος λάτρης του σκακιού και του προγραμματισμού, αλλά το τυπικό σκάκι σύντομα έγινε βαρετό γι 'αυτόν, οπότε άρχισε να διασκεδάζει με τα κομμάτια του πύργου.

Βρήκε μια σκακιέρα με Ν σειρές και Ν στήλες και τοποθέτησε πάνω της Κ πύργους. Το παιχνίδι του Mirko αποτελείται από τους ακόλουθους κανόνες:

1. Η ισχύς κάθε πύργου καθορίζεται από έναν ακέραιο αριθμό.
2. Ένας πύργος βλέπει όλα τα πεδία που βρίσκονται στη σειρά ή στη στήλη του εκτός από το δικό του πεδίο.
3. Λέμε ότι ένα πεδίο δέχεται επίθεση εάν το δυαδικό XOR όλων των δυνάμεων των rooks που βλέπουν το πεδίο είναι μεγαλύτερο από 0.

Παρατηρήστε ότι το πεδίο στο οποίο βρίσκεται ένας πύργος μπορεί να δεχθεί επίθεση ή όχι.

Αρχικά, ο Mirko τοποθέτησε τους πύργους σε μια συγκεκριμένη διάταξη στον πίνακα και θα κάνει P κινήσεις.
Μετά από κάθε κίνηση, προσδιορίστε πόσα πεδία δέχονται επίθεση.
Κάθε πύργος μπορεί να μετακινηθεί σε οποιοδήποτε ελεύθερο πεδίο σε ολόκληρο τον πίνακα (όχι μόνο σε στήλη και γραμμή).

Είσοδος

Η πρώτη γραμμή εισόδοου περιέχει ακέραιους αριθμούς N, K, P ~(1 \leq~ N ~\leq 1\,000\,000\,000,\;1 \leq~ K ~\leq 100\,000,\;1 \leq~ P ~\leq 100\,000)~.
Κάθε μία από τις ακόλουθες K γραμμές περιέχει τρεις ακέραιους αριθμούς R, C, X ~(1 \leq~ R, C ~\leq~ N~,\;1 \leq~ X ~\leq 1\,000\,000\,000)~ που δηλώνουν ότι αρχικά υπάρχει ένας πύργος ισχύος X στο πεδίο (R, C).
Κάθε μία από τις ακόλουθες P γραμμές περιέχει τέσσερις ακέραιους R₁, C₁, R₂, C₂, ~(1 \leq~ R₁, C₁, R₂, C₂ ~\leq~ N~)~ που δηλώνουν ότι ο πύργος έχει μετακινηθεί από πεδίο (R₁, C₁) σε πεδίο (R₂, C₂).
Είναι εγγυημένο ότι δεν θα υπάρχουν δύο πύργοι σε ένα πεδίο σε κανένα σημείο.

Έξοδος

Η έξοδος πρέπει να αποτελείται από P γραμμές, με την ~k~-οστή γραμμή να περιέχει τον συνολικό αριθμό των πεδίων που δέχονται επίθεση μετά από k κινήσεις.

Βαθμολογία

Σε περιπτώσεις δοκιμών αξίας 25% των συνολικών πόντων, τα N και K δεν θα υπερβαίνουν τους 100.

Παραδείγματα

input

2 2 2
1 1 1
2 2 1
2 2 2 1
1 1 1 2

output

4
0

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

Μετά την πρώτη κίνηση, κάθε πεδίο στο ταμπλό δέχεται επίθεση. Για παράδειγμα, το πεδίο ~(1,\;1)~ φαίνεται μόνο από έναν πύργο, οπότε το συνολικό XOR για αυτό το πεδίο είναι 1. Μετά τη δεύτερη κίνηση κανένα από τα πεδία δεν δέχεται επίθεση. Για παράδειγμα, το πεδίο ~(1,\;1)~ φαίνεται και από τους δύο πύργους, οπότε το συνολικό XOR για αυτό το πεδίο είναι 0.

input

2 2 2
1 1 1
2 2 2
2 2 2 1
1 1 1 2

output

4
2

input

3 3 4
1 1 1
2 2 2
2 3 3
2 3 3 3
3 3 3 1
1 1 1 2
3 1 3 2

output

6
7
7
9