Nekameleoni

"Γεια! Έχω μια φοβερή αποστολή με χαμαιλέοντες, 5η εργασία για τον διαγωνισμό του Σαββάτου."
"Συνέχισε..."

(...)

"Αυτό είναι πολύ δύσκολο, έχω ένα πιο εύκολο, δεν θα το έλυναν".
"Σας δίνεται ένας πίνακας ~N~ ακεραίων από το διάστημα ~[1,\;K]~. Πρέπει να επεξεργαστείτε ~M~ ερωτήματα. Ο πρώτος τύπος ερωτήματος απαιτεί από εσάς να αλλάξετε έναν αριθμό στον πίνακα σε διαφορετική τιμή και ο δεύτερος τύπος ερωτήματος απαιτεί να προσδιορίσετε το μήκος του συντομότερου συνεχόμενου υποπίνακα του τρέχοντος πίνακα που περιέχει όλους τους αριθμούς από το 1 έως το ~K~."
"Χμ, μπορώ να το κάνω σε ~O(N^6)~. Ποιο είναι το όριο για το \(Ν\);"

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τους ακέραιους ~N~, ~K~ και ~M~ ~(1 \leq N,\;M \leq 100\,000,\;1 \leq K \leq 50)~. Η δεύτερη γραμμή εισόδου περιέχει \(Ν\) ακέραιους που χωρίζονται με κενό, τους ακέραιους από τον πίνακα. Μετά από αυτό,ακολουθούν ~M~ ερωτήματα, το καθένα σε μία από τις ακόλουθες δύο μορφές:

• "1 p v" - αλλάξτε την τιμή του ~p~-οστού αριθμού σε ~v\;(1 \leq p \leq N,\;1 \leq v \leq K)~
• "2" - ποιό είναι το μήκος του συντομότερου συνεχόμενου υποπίνακα του πίνακα που περιέχει όλους τους ακέραιους αριθμούς από το ~1~ έως το ~K~

Έξοδος

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

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας 30% των συνολικών πόντων, θα έχει ~1 \leq N,\;M \leq 5\,000~.

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

input

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

output

3
-1
4

input

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

output

3
3
4