Zero-G là môi trường không trọng lực mà một tàu chở hàng liên hành tinh đang trôi dạt. Tàu mang theo ~n~ thùng hàng xếp thành một hàng dọc, đánh số thứ tự từ ~1~ đến ~n~. Thùng thứ ~i~ mang mã loại hàng là một số nguyên ~a_i~ (mã chỉ dùng để phân biệt các loại hàng).

Để đảm bảo chuyến bay diễn ra an toàn, mỗi loại hàng trên tàu phải có số lượng thùng nằm trong một mức nhất định: quá ít thì không đủ phục vụ hành trình, quá nhiều thì làm mất cân bằng tải trọng trong môi trường không trọng lực. Vì vậy, cơ quan kiểm định đưa ra hai ngưỡng ~A~ và ~B~ (~A \le B~). Khi kiểm tra một đoạn thùng hàng liên tiếp:

• Với mỗi loại hàng ~x~, gọi ~c_x~ là số lượng thùng loại x xuất hiện trong đoạn đó.
• Loại hàng ~x~ được gọi là an toàn nếu số lượng thùng của nó thỏa mãn: ~A \le c_x \le B~

Lưu ý: Điều kiện kiểm định chỉ xét trên số lượng thùng ~c_x~, không phụ thuộc vào giá trị mã ~x~. Loại hàng không xuất hiện trong đoạn có ~c_x = 0~, do ~A \ge 1~ nên không được tính là an toàn.

Có ~q~ đợt kiểm định. Mỗi đợt yêu cầu kiểm tra một đoạn từ thùng ~l~ đến thùng ~r~. Hãy đếm số loại hàng an toàn trong từng đợt kiểm định.

Dữ liệu vào

• Dòng đầu tiên chứa bốn số nguyên ~n, q, A, B~ (~1 \le n, q \le 10^6~; ~1 \le A \le B \le n~).
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le n~) — mã loại hàng của các thùng.
• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l, r~ (~1 \le l \le r \le n~) mô tả một đoạn cần kiểm định.

Dữ liệu ra

In ra ~q~ dòng, dòng thứ ~j~ là số loại hàng an toàn của đợt kiểm định thứ ~j~.

Ví dụ

Input

10 5 2 3
1 2 1 3 2 1 2 2 3 1
1 10
2 6
3 8
4 9
1 4

Output

1
2
2
2
1

Giải thích ví dụ (đợt 1 với ~l = 1, r = 10~ và ~A = 2, B = 3~):

Đoạn ~[1, 10]~ chứa toàn bộ các thùng: 1 2 1 3 2 1 2 2 3 1.

Chỉ có loại hàng 3 an toàn nên kết quả là 1.

Subtask