Một trang game online xếp hạng người chơi theo thời gian thực. Ban đầu có N_init game thủ với số điểm tương ứng. Sau đó có Q sự kiện, mỗi sự kiện thuộc một trong hai loại:

• 1 x: một game thủ mới đạt được x điểm.
• 2: hệ thống cần in ra số điểm cao thứ K trong tất cả game thủ hiện tại. Nếu số game thủ hiện tại < K, in -1.

Hãy giúp hệ thống xử lý các sự kiện.

Đầu vào

• Dòng đầu chứa ba số nguyên N_init (1 ≤ N_init ≤ 10^5), K (1 ≤ K ≤ 10^5), Q (1 ≤ Q ≤ 10^5).
• Dòng hai chứa N_init số nguyên — điểm số ban đầu.
• Q dòng tiếp theo, mỗi dòng mô tả một sự kiện.

Đầu ra

Với mỗi sự kiện loại 2, in kết quả trên một dòng riêng.

Ví dụ

Input:
5 3 6
2 5 1 8 3
2
1 7
2
1 4
1 9
2

Output:
3
5
7