RMT

Το Rail Metro Transit (RMT) λειτουργεί ένα πολύ ασυνήθιστο σύστημα μετρό. Υπάρχουν ~N~ σταθμοί μετρό αριθμημένοι από το ~1~ έως το ~N~. Υπάρχουν ~M~ γραμμές του μετρό αριθμημένες από το ~1~ έως το ~M~, με κάθε σταθμό να ανήκει ακριβώς σε μία γραμμή και υπάρχει τουλάχιστον ένας σταθμός ανά γραμμή. Οι γραμμές του μετρό είναι κυκλικές. Δηλαδή, αν ένας σταθμός έχει τον αριθμό ~S~, ο επόμενος σταθμός μετά τον S, είναι ο σταθμός της ίδιας γραμμής με τον αμέσως μεγαλύτερο αριθμό, εκτός αν ο ~S~ είναι ο μεγαλύτερος αριθμός σταθμού της γραμμής, οπότε ο επόμενος σταθμός μετά τον ~S~, είναι ο σταθμός της ίδιας γραμμής με τον μικρότερο αριθμό.

Η RMT διεξάγει έναν έλεγχο φορτίου για το συστήμά της με τη βοήθεια εθελοντών επιβατών που θα ταξιδέψουν με τα τρένα του μετρό. Ο έλεγχος ξεκινά με ένα τρένο του μετρό σε κάθε σταθμό και για κάθε ~i~, υπάρχουν ~A_{i}~ επιβάτες στο τρένο στο σταθμό ~i~. Οι εθελοντές καθ'όλη τη διάρκεια του ελέγχου παραμένουν στα τρένα που τους έχουν ανατεθεί.

Καθ' όλη τη διάρκεια του ελέγχου, η RMT θα εκτελεί ~Q~ ενέργειες. Κάθε μία από τις ~Q~ ενέργειες, θα είναι μία από τις εξής δύο: είτε θα ερευνήσει το συνολικό αριθμό των επιβατών των τρένων στους σταθμούς που αριθμούνται από ~l~ έως ~r~, είτε θα λειτουργήσουν όλα τα τρένα σε κάποια γραμμή ~x~. Όταν ένα τρένο στη γραμμή ~x~ λειτουργεί, πηγαίνει στον επόμενο σταθμό της γραμμής.

Είστε ο μεγαλύτερος θαυμαστής της RMT, οπότε προσφερθήκατε πολύ γενναιόδωρα να παρακολουθήσετε τις ενέργειες της RMT και να αναφέρετε τις απαντήσεις στις έρευνές τους.

Είσοδος

Η πρώτη γραμμή θα περιέχει τρεις ακέραιους αριθμούς ~N~ , ~M~ και ~Q\;(1 \le M \le N \le 150\;000,\;1 \le Q \le 150\;000)~. Η δεύτερη γραμμή θα περιέχει τους αριθμούς των γραμμών του μετρό στις οποίες ανήκει κάθε σταθμός από το ~1~ έως το ~N~: ~L_{1}~, ~L_{2}~, . . . . , ~L_{N}~ . Η τρίτη γραμμή θα περιέχει ~N~ ακέραιους αριθμούς ~A_{1}~, ~A_{2}~, . . . . , ~A_{N}~ ~(1 \le A_{i} \le 7000)~ που αντιπροσωπεύουν τον αρχικό αριθμό επιβατών σε κάθε σταθμό από το ~1~ έως το ~N~. Οι επόμενες ~Q~ γραμμές θα έχουν η καθεμιά, μία από τις ακόλουθες μορφές:

• ~1\;l\;r~, η οποία αντιπροσωπεύει μια έρευνα ~(1 \le l \le r \le N)~.
• ~2\;x~, η οποία αντιπροσωπεύει τη γραμμή ~x~ της ~RMT~ που βρίσκεται σε λειτουργεία ~(1 \le x \le M)~.

Για ~2~ από τους ~15~ διαθέσιμους βαθμούς, ~N \le 1000~ και ~Q \le 1000~.

Για επιπλέον ~2~ από τους ~15~ διαθέσιμους βαθμούς, ~L_{i} \le L_{i +1}~ ~(1 \le i < N)~.

Για επιπλέον ~3~ από τους ~15~ διαθέσιμους βαθμούς, ~M \le 200~.

Για επιπλέον ~3~ από τους ~15~ διαθέσιμους βαθμούς, δεν θα υπάρχουν περισσότερα από ~200~ τρένα σε οποιαδήποτε γραμμή.

Έξοδος

Για κάθε έρευνα, εξάγετε το αποτέλεσμα της έρευνας σε ξεχωριστή γραμμή.

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

input

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

output

15
10
9

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

Το σύστημα του μετρό απεικονίζεται παρακάτω, με τους σταθμούς να αριθμούνται από το ~1~ έως το ~5~ και τις γραμμές που συνδέουν τους σταθμούς να σημειώνονται είτε ως γραμμή ~1~ είτε ως γραμμή ~2~:

Αρχικά, ο αριθμός των επιβατών σε κάθε σταθμό είναι {~1~, ~2~, ~3~, ~4~, ~5~}.

Η απάντηση στην πρώτη έρευνα είναι ~1 + 2 + 3 + 4 + 5 = 15~.

Μετά τη λειτουργία της γραμμής ~1~, ο αριθμός των επιβατών σε κάθε σταθμό είναι {~3~, ~2~, ~1~, ~4~, ~5~}.

Η απάντηση στη δεύτερη έρευνα είναι ~1 + 4 + 5 = 10~.

Αφού λειτουργήσει η γραμμή ~2~, ο αριθμός των επιβατών σε κάθε σταθμό είναι {~3~, ~5~, ~1~, ~2~, ~4~}.

Η απάντηση στην τρίτη έρευνα είναι ~3 + 5 + 1 = 9~.

input

3 1 7
1 1 1
114 101 109
1 1 1
2 1
1 1 1
2 1
1 1 1
2 1
1 1 1

output

114
109
101
114

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

Το σύστημα του μετρό απεικονίζεται παρακάτω, με τους σταθμούς να αριθμούνται από το ~1~ έως το ~3~ και τις γραμμές που συνδέουν τους σταθμούς να είναι όλες η γραμμή ~1~:

Λίγο πριν από την πρώτη έρευνα, ο αριθμός των επιβατών σε κάθε σταθμό είναι {~114~, ~101~, ~109~}.
Λίγο πριν από τη δεύτερη έρευνα, ο αριθμός των επιβατών σε κάθε σταθμό είναι {~109~, ~114~, ~101~}.
Λίγο πριν από την τρίτη έρευνα, ο αριθμός των επιβατών σε κάθε σταθμό είναι {~101~, ~109~, ~114~}.
Λίγο πριν από την τέταρτη έρευνα, ο αριθμός των επιβατών σε κάθε σταθμό είναι {~114~, ~101~, ~109~}.