Chia kẹo

Có \(N\) hộp kẹo, hộp thứ \(i\) ban đầu có \(a_i\) viên (\(1 \le a_i \le 10^5\)).
Có \(K\) học sinh lần lượt đến lấy kẹo. Mỗi học sinh lấy đúng \(1\) viên, và luôn lấy từ hộp còn nhiều kẹo nhất.
Nếu có nhiều hộp cùng nhiều nhất, học sinh có thể lấy ở bất kỳ hộp nào trong số đó.

Sau khi \(K\) học sinh đã lấy xong, hãy in ra thống kê:
Với mỗi giá trị \(x\) xuất hiện trong dãy \(a\) cuối cùng, in một dòng gồm hai số \(x\) và số hộp còn đúng \(x\) viên, theo thứ tự tăng dần của \(x\).

Input

• Dòng đầu chứa hai số nguyên \(N, K\) (\(1 \le N \le 10^5\), \(0 \le K \le 10^9\)).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(0 \le a_i \le 10^5\)).

Đảm bảo \(K \le a_1 \; + a_2 \; + \cdots \; + a_n.\)

Output

In ra thống kê số hộp còn lại theo định dạng: mỗi dòng một cặp số \(x\) và số hộp còn \(x\) viên, theo thứ tự tăng dần của \(x\). Lưu ý chỉ in ra những \(x\) với số lần xuất hiện lớn hơn \(0\).

Input

5 4
3 1 2 2 5

Output

1 1
2 4

Notes

Ban đầu: \((3,1,2,2,5)\).

• HS1 lấy ở hộp 5 \(\to\) (3,1,2,2,4).
• HS2 lấy ở hộp 5 \(\to\) (3,1,2,2,3).
• HS3 lấy ở hộp 5 \(\to\) (3,1,2,2,2).
• HS4 lấy ở hộp 1 \(\to\) (2,1,2,2,2).

Kết quả cuối: \((2,1,2,2,2)\). Thống kê: \(1\) hộp có \(1\) viên, \(4\) hộp có \(2\) viên.

Scoring

• Subtask 1 (50% số điểm): \(N \le 1000\), \(K \le 1000\).
• Subtask 2 (30% số điểm): \(N \le 10^5\), \(K \le 10^4\).
• Subtask 3 (20% số điểm): \(N \le 10^5\), \(K \le 10^9\).