Reimu hiện đang hết tiền nên đã nhờ Marisa bắt cho ~n~ con tắc kè để đem bán, con tắc kè thứ ~i~ có màu ~A_i~. Có ~q~ ngày, mỗi ngày sẽ có một trong những sự kiện sau diễn ra:

• Con tắc kè thứ ~i~ đổi thành màu ~x~.
• Có khách đến xem các con tắc kè thứ ~l~ đến ~r~. Người khách cần biết xem có bao nhiêu màu có đúng ~k~ con tắc kè.

Vì có quá nhiều tắc kè nên Reimu nhờ các bạn đếm hộ cô nhé!

Có rất nhiều khách đến xem tắc kè nhưng đáng tiếc là khách không bao giờ mua. Reimu nghèo vẫn hoàn nghèo, ăn tắc kè thay cơm.

Input

• Dòng đầu tiên gồm ba số nguyên ~n,q,k~.
• Dòng thứ hai gồm ~n~ số nguyên ~1 \le A_i \le n~, màu của những con tắc kè.
• ~q~ dòng tiếp theo, là sự kiện của các ngày:
  • Sự kiện thứ nhất dạng 1 i x, con tắc kè thứ ~i~ đổi thành màu ~x~.
  • Sự kiện thứ hai dạng 2 l r, người khách đến xem những con tắc kè từ ~l~ đến ~r~.

Output

• Với mỗi sự kiện loại hai, bạn cần in ra số lượng màu tắc kè xuất hiện chính xác ~k~ lần.

Sample test

Input

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

Output

2
1
1
1

Ràng buộc

• Subtask 1 ~(30\%)~: ~1 \le n, q \le 1000~.
• Subtask 2 ~(20\%)~: ~1 \le n, q \le 10^5, A_i \le 10~.
• Subtask 3 ~(30\%)~: ~1 \le n, q \le 4 \times 10^5~, tắc kè không đổi màu.
• Subtask 4 ~(20\%)~: ~1 \le n, q \le 7 \times 10 ^4~.