Rotiraj

Ο Mislav και ο Marko έχουν επινοήσει ένα νέο παιχνίδι, το δημιουργηκά ονομασμένο Rotate. Πρώτον, ο Mirko φαντάζεται μια αριθμητική ακολουθία μήκους ~N~ και τη χωρίζει σε τμήματα, με κάθε τμήμα να περιέχει ~K~ αριθμούς (το ~K~ διαιρεί ομοιόμορφα το ~N~). Το πρώτο τμήμα περιέχει αριθμούς στις πρώτες ~K~ θέσεις της ακολουθίας, το δεύτερο τμήμα τις ακόλουθες ~K~ θέσεις και ούτω καθεξής.
Στη συνέχεια, ο Marko ζητά από τον Mislav να εφαρμόσει έναν αριθμό πράξεων στην ακολουθία, με κάθε πράξη να είναι ένας από τους ακόλουθους δύο τύπους:

1. Περιστρέψτε τους αριθμούς σε κάθε τμήμα προς τα αριστερά/δεξιά κατά ~X~ θέσεις
2. Περιστρέψτε ολόκληρη την ακολουθία προς τα αριστερά/δεξιά κατά ~X~ θέσεις
   Παρατηρήστε ότι μια πράξη τύπου 2 μπορεί να αλλάξει τους αριθμούς που ανήκουν σε κάθε τμήμα. Αφού εφαρμόσει όλες τις πράξεις, ο Mislav αποκαλύπτει την τελευταία σειρά στον Marko. Το καθήκον του Marko είναι να βρει την αρχική σειρά του Mislav. Σας έχει ζητήσει βοήθεια.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τρεις θετικούς ακέραιους αριθμούς: ~N~ ~(1 \le N \le 100\,000)~, το μήκος της ακολουθίας, ~K~ ~(1 \le K \le 100\,000)~, το μέγεθος κάθε τμήματος και ~Q~ ~(1 \le Q \le 100\,000)~, ο αριθμός των πράξεων.
Κάθε μία από τις ακόλουθες γραμμές ~Q~ περιέχει δύο ακέραιους αριθμούς: ~A~ ~(1 \le A \le 2)~, τον τύπο πράξης και ~X~ ~(-100\,000 \le X \le 100\,000)~, τον αριθμό των θέσεων που πρέπει να περιστραφούν. Ένας αρνητικός αριθμός αντιπροσωπεύει περιστροφή προς τα αριστερά, ενώ ένας θετικός αντιπροσωπεύει περιστροφή προς τα δεξιά.
Η τελευταία γραμμή εισόδου περιέχει ~N~ ακέραιους αριθμούς ~Z_i~ ~(0 \le Z_i \le 100\,000)~ χωρισμένους σε διάστημα που αντιπροσωπεύουν την τελική ακολουθία (μετά την εφαρμογή όλων των πράξεων).

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει την απαιτούμενη αρχική ακολουθία.

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας τουλάχιστον ~40~% των συνολικών πόντων, το ~N~ θα είναι το πολύ 100.
Σε δοκιμαστικές περιπτώσεις αξίας τουλάχιστον ~70~% των συνολικών πόντων, το ~K~ θα είναι το πολύ 100.

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

input

4 2 2
2 2
1 1
3 2 1 0

output

0 1 2 3

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

Η αρχική ακολουθία είναι ~0\;1\;2\;3~. Μετά τις πρώτες πράξεις, η ακολουθία είναι ~2\;3\;0\;1~, και μετά τη δεύτερη πράξη, γίνεται ~3\;2\;1\;0~. Αυτό αντιστοιχεί στην τελική ακολουθία.

input

8 4 4
1 3
1 15
1 -5
2 -1
6 10 14 19 2 16 17 1

output

6 10 14 1 2 16 17 19

input

9 3 5
1 1
2 -8
2 9
1 1
2 -4
3 1 8 7 4 5 2 6 9

output

5 3 6 9 7 1 8 2 4