Người dân thành phố SQRT đang chuẩn bị đón Tết Ất Tỵ 2025.

Năm nay, do kinh tế khó khăn, chính quyền thành phố muốn tái sử dụng những món đồ trang trí Tết từ những năm trước đó. Một trong số đó là một dãy đèn lồng với nhiều màu sắc rực rỡ.

Dãy đèn lồng gồm \(n\) chiếc được đánh số từ \(1\) đến \(n\). Chiếc đèn thứ \(i\) có màu \(a_i\). Chính quyền muốn chọn ra một đoạn gồm ít nhất \(k\) chiếc đèn liên tiếp trong dãy để sử dụng trong năm mới, và thay thế một số chiếc đèn trong đoạn này sang một màu khác sao cho sau khi thay thế thì đoạn gồm tối đa \(x\) màu khác nhau. Chi phí để thay thế một chiếc đèn sang màu khác là \(1\) đồng.

Chính quyền muốn thử nghiệm \(q\) phương án, mỗi phương án là một cặp số \((k, x)\) khác nhau. Với mỗi phương án, họ cần tính toán chi phí tối thiểu để có thể tạo ra đoạn đèn trang trí thỏa mãn yêu cầu.

Yêu cầu

Là một lập trình viên chuyên thực hiện những nhiệm vụ tính toán cho chính quyền thành phố, bạn hãy viết một chương trình giải quyết phương án thử nghiệm trên trong thời gian ngắn nhất.

Input

• Dòng đầu tiên gồm ba số nguyên dương \(n, q, c\) (\(1 \le c \le n \le 10^5\), \(1 \le q \le 400\)).
• Dòng tiếp theo gồm \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le c\)).
• \(q\) dòng tiếp theo, mỗi dòng gồm hai số nguyên dương \(k, x\) (\(1 \le k \le n\), \(1 \le x \le c\)).

Output

• Với mỗi phương án thử nghiệm, in ra chi phí nhỏ nhất tìm được trên một dòng.

Ràng buộc bổ sung

• \(20\%\) số điểm có \(n \le 200\) và \(c = 2\).
• \(20\%\) số điểm khác có \(c = 2\).
• \(20\%\) số điểm khác có \(x = 1\) trong mọi phương án.
• \(10\%\) số điểm khác có \(q = 1\).
• \(10\%\) số điểm khác có \(k\) giống nhau trong mọi phương án.
• \(10\%\) số điểm khác có \(q \le 30\).
• \(10\%\) số điểm còn lại không có giới hạn gì thêm.

Example

5 2 3
1 2 1 2 3
5 2
3 1

1
1