Victor có một bộ sưu tập các bài hát dân gian rất lớn, các bài hát được đánh số từ ~1~ đến ~n~ (~1 \le n < 10^6~). Khi nghe nhạc, danh mục tất cả các bài hát không thể hiển thị lên màn hình. Cửa sổ quản lý bài hát chỉ cho phép chứa thông tin về ~k~ bài liên tiếp nhau trong danh sách lưu trữ, dĩ nhiên, trong đó luôn luôn bao gồm bài hát Victor đang nghe.

Khi tên bài hát lần đầu tiên xuất hiện trên màn hình, phần mềm phải mở file đọc các thuộc tính như tên ca sỹ, tác giả v.v. Thông tin này được lưu lại trong phòng đệm hệ thống. Vì vậy, khi tên bài hát đã hiển thị xuất hiện lại hệ thống không phải mở file để truy nhập tới các thuộc tính của nó.

Yêu cầu: Cho biết các số nguyên ~n~, ~k~ và ~m~ – số lượng các bài hát Victor định nghe và danh sách các bài hát đó (có thể có những bài hát được nghe nhiều lần, vì vậy danh sách có thể chứa các số giống nhau). Hãy xác định số lần tối thiểu hệ thống cần mở file và chỉ ra một cách hiển thị bài hát trên cửa sổ.

Input

• Dòng đầu tiên chứa 2 số nguyên ~n~ và ~k~ (~1 \le k < n; k \le 1000~).
• Dòng thứ 2 chứa số nguyên ~m~ (~1 \le m \le 300\,000~).
• Dòng thứ ~i~ trong ~m~ dòng sau chứa một số nguyên – bài hát thứ ~i~ cần nghe.

Output

• Dòng đầu tiên chứa số nguyên ~p~ – số lần mở file.
• Mỗi dòng trong ~m~ dòng sau chứa 2 số nguyên ~a~ và ~b~ xác định danh sách bài hát hiển thị (~b = a + k - 1~).

Sample Input 1

15 4
6
6
14
11
3
8
5

Sample Output 1

10
3 6
11 14
11 14
3 6
5 8
3 6