Modern Art

Ένας νέος και ανερχόμενος καλλιτέχνης έχει έναν μοναδικό τρόπο να δημιουργεί καρό μοτίβα. Η ιδέα είναι ότι χρησιμοποεί έναν καμβά διαστάσεων ~M \times N~, ο οποίος αρχικά είναι εξ ολοκλήρου μαύρος. Στη συνέχεια ο καλλιτέχνης επιλέγει επανειλημμένα μια γραμμή ή μια στήλη και περνάει το "μαγικό" του πινέλο κατά μήκος της γραμμής ή της στήλης. Το πινέλο αλλάζει το χρώμα κάθε κελιού στη γραμμή ή τη στήλη από μαύρο σε χρυσό ή από χρυσό σε μαύρο.

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

Είσοδος

Η πρώτη γραμμή εισόδου θα περιέχει έναν θετικό ακέραιο αριθμό ~M~. Η δεύτερη γραμμή εισόδου θα περιέχει έναν θετικό ακέραιο αριθμό ~N~. Η τρίτη γραμμή εισόδου θα περιέχει έναν θετικό ακέραιο αριθμό ~K~. Η είσοδος θα αποτελείται επίσης από ~K~ γραμμές που θα δίνουν τις επιλογές που κάνει ο καλλιτέχνης. Κάθε μία από αυτές τις γραμμές θα περιέχει είτε το ~R~ ακολουθούμενο από ένα κενό και στη συνέχεια έναν ακέραιο αριθμό που είναι ο αριθμός γραμμής, είτε το ~C~ ακολουθούμενο από ένα κενό και στη συνέχεια έναν ακέραιο αριθμό που είναι ο αριθμός στήλης. Οι γραμμές αριθμούνται από πάνω προς τα κάτω από το ~1~ έως το ~M~. Οι στήλες αριθμούνται από αριστερά προς τα δεξιά από το ~1~ έως το ~N~.

Ο ακόλουθος πίνακας δείχνει πώς κατανέμονται οι ~15~ διαθέσιμοι βαθμοί.

~1~ βαθμός	~M = 1~	~N = 1~	~K \le 100~	Mόνο ένα κελί, και έως και ~100~ επιλογές από τον καλλιτέχνη
~4~ βαθμοί	~M = 1~	~N \le 100~	~K \le 100~	Μόνο μία γραμμή, και έως και 100 επιλογές από τον καλλιτέχνη
~5~ βαθμοί	~M \le 100~	~N \le 100~	~K \le 100~	Έως ~100~ γραμμές, έως ~100~ στήλες και έως και ~100~ επιλογές από τον καλλιτέχνη
~5~ βαθμοί	~M \le 5000000~	~N \le 5000000~	~K \le 5000000~	Έως ~5000000~ κελιά, και έως ~1000000~ επιλογές από τον καλλιτέχνη

Έξοδος

Εξάγετε έναν μη αρνητικό ακέραιο που να ισούται με τον αριθμό των κελιών που είναι χρυσά στο μοτίβο που ορίζεται από τις επιλογές του καλλιτέχνη.

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

input

3
3
2
R 1
C 1

output

4

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

Αφού περάσει το πινέλο κατά μήκος της πρώτης γραμμής, ο καμβάς μοιάζει ως εξής:

~GGG~
~BBB~
~BBB~

Στη συνέχεια, αφού περάσει το πινέλο κατά μήκος της πρώτης στήλης, τέσσερα κελιά είναι χρυσά στο τελικό μοτίβο που ορίστηκε από τις επιλογές του καλλιτέχνη:

~BGG~
~GBB~
~GBB~

input

4
5
7
R 3
C 1
C 2
R 2
R 2
C 1
R 4

output

10

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

Δέκα κελιά είναι χρυσά στο τελικό μοτίβο που ορίζεται από τις επιλογές του καλλιτέχνη:

~BGBBB~
~BGBBB~
~GBGGG~
~GBGGG~