Во последните години панаѓурите се организираат на некоја од најдолгите улици во градот. Улицата се забранува за сообраќај и на неа ќе се изнаредат тезгите една до една. Иако панаѓурите знаат да бидат големи со по N тезги луѓето знаат дека генерално стоката која се нуди е со ограничен избор, односно постојат вкупно K типови на тезги (да ги означиме со броевите од 1 до K).

Главното прашање на секој панаѓурец е како да помине најмал пат, односно најмалку последователни тезги, а да биде сигурен дека поминал покрај барем една тезга од секој тип. Нас не интересира колкав е тој минимален број на последователни тезги! Од друга страна, градоначалникот добива ургенции во секоја минута, па некои тезги ги доделува на друг, а со тоа тезгата го менува типот. Иако градоначалникот има чувство дека некому направил услуга, понекогаш таква негова одлука го прави патот подолг, а понекогаш го скратува.

Во оваа задача на почеток ја имате првичната распределба на типовите за секоја од N-те тезги. Ваша задача е да испроцесирате М прашанки од 2 типа. Првиот тип се однесува на „белјата“ што ја прави градоначалникот, односно од вас се бара да го промените типот на конкретна тезга. Вториот тип бара од вас да го утврдите погоре дефинираниот минимален број на тезги (последователни тезги во кои се наоѓаат тезги од сите K различни типови).

Паднало снег, панаѓурот може да го откажат, но вие сепак треба да почнете да ја решавате задачата.

Влез

Во првиот ред се запишани броевите N, K и M (1 ≤ N, M ≤ 100 000, 1 ≤ K ≤ 50).
Во вториот ред се запишани N цели броеви кои ги даваат типовите на секоја тезга, според првичниот распоред.
Потоа следат M редови кои опишуваат исто толку прашанки, секоја во една од следните форми:
● "1 p v" - промени го типот на p-тата тезга во v (1 ≤ p ≤ N, 1 ≤ v ≤ K)
● "2" - кој е минималниот број на последователни тезги во кои се наоѓаат тезги од сите K различни типови.

Бодување: Кај тест случаи кои носат 30% од поените важи дека 1 ≤ N, M ≤ 5 000.

Излез

Во излезот, за секоја прашанка од тип 2 во посебен ред отпечатете го одговорот. Ако бараната низа не постои отпечатете −1.

Ограничувања

Временско ограничување: 3 seconds
Мемориско ограничување: 512 megabytes

Примери

влез
4 3 5 
2 3 1 2 
2 
1 3 3 
2 
1 1 1 
2

излез
3 
-1 
4

влез
6 3 6 
1 2 3 2 1 1 
2 
1 2 1 
2 
1 4 1 
1 6 2 
2

излез
3 
3 
4

Објаснување за првиот тест пример: Има 4 тезги од 3 типови. Во првичниот распоред првата тезга е од тип 2, втората од тип 3, третата од тип 1 и четвртата од тип 2 (распоредот по типови е: 2, 3, 1, 2). Одговорот на првата прашанка е 3 (во првите три последователни тезги се наоѓаат тезги од сите типови). Со прашанката "1 3 3" се случува промена на 3-рата тезга во тезга од тип 3. Сега распоредот на тезги по типови е: (2, 3, 3, 2) . Во овој распоред нема тезга од тип 1, па затоа одговорот на следната прашанка "2" е -1. По прашанката "1 1 1" редоследот е: (1, 3, 3, 2). Одговорот на последната прашанка "2" е 4 затоа што во најмалку 4 последователни тезги се наоѓаат тезги од сите 3 типови.