Để tạo không khí sôi động trong buổi học toán cuối năm, thầy giáo viết lên bảng ~2~ số nguyên dương ~a~ và ~b~. Sau đó thầy đề nghị An và Bình mỗi người đưa ra một số nguyên dương bất kỳ, câu trả lời của An là số ~n~ và câu trả lời của Bình là số ~m~. An phải xác định số lượng các số nguyên trong phạm vi từ ~a~ đến ~b~ và chia hết cho ~n~, còn Bình phải xác định số lượng các số nguyên trong phạm vi từ ~a~ đến ~b~ và chia hết cho ~m~. Bạn lớp trưởng phải thông báo hiệu số của kết quả đúng của An với kết quả đúng của Bình.

Yêu cầu: Hãy xác định số mà bạn lớp trưởng thông báo.

Input

Dữ liệu vào từ bàn phím gồm một dòng chứa ~4~ số nguyên dương ~a, b, n, m~. Các số cách nhau một dấu cách (~0 < a, b, n, m \le 2 \times 10^9~, ~a < b~).

Output

Kết quả in ra màn hình số mà bạn lớp trưởng thông báo.

Sample Input 1

2 9 2 3

Sample Output 1

1

Số tự nhiên ~y~ chia hết cho số tự nhiên ~x~ thì ~x~ được gọi là ước của ~y~.

Trong một giờ học môn Toán, sau khi học xong kiến thức về ước của số tự nhiên, để củng cố kiến thức cho học sinh, thầy giáo tổ chức một trò chơi như sau:

Cho trước dãy ~\{a\}~ gồm ~n~ số tự nhiên ~a_1, a_2, \dots, a_n~. Có ~q~ học sinh tham gia trò chơi. Với mỗi học sinh tham gia trò chơi, thầy sẽ đưa ra hai số tự nhiên ~l~ và ~r~ (~1 \le l \le r \le n~). Nhiệm vụ của học sinh đó là tính tổng số lượng ước của các số tự nhiên trong dãy ~a_l, a_{l+1}, \dots, a_r~.

Yêu cầu: Hãy tính tổng số lượng ước của các số trong đoạn ~[l, r]~ cho mỗi học sinh.

Input

• Dòng đầu tiên gồm hai số tự nhiên ~n~ và ~q~ (~1 \le n, q \le 10^6~) tương ứng là số lượng số trong dãy ~\{a\}~ và số học sinh tham gia trò chơi.
• Dòng thứ hai gồm ~n~ số tự nhiên ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^6~).
• ~q~ dòng tiếp theo, mỗi dòng gồm hai số tự nhiên ~l~ và ~r~ (~1 \le l \le r \le n~).

Output

• In ra màn hình kết quả tính được của ~q~ học sinh, mỗi kết quả trên một dòng.

Sample Input 1

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

Sample Output 1

5
10
11

Nhà xuất bản X đang in một series truyện dài gồm ~n~ chương, chương thứ ~i~ có ~a_i~ trang (~1 \le i \le n~). Ban biên tập quyết định in thành ~k~ tập, sao cho mỗi chương phải nằm gọn trong một tập, tập ~1~ bao gồm một hoặc một số chương đầu tiên, mỗi tập tiếp theo bao gồm một hoặc một số chương tiếp theo. Thứ tự các chương xuất hiện từ tập ~1~ đến tập thứ ~k~ đảm bảo là các chương liên tiếp từ chương thứ ~1~ đến chương thứ ~n~.

Ban biên tập có nhiệm vụ phân chia ~n~ chương thành ~k~ tập sao cho số trang của tập dày nhất là ít nhất.

Yêu cầu: Hãy xác định số trang của tập dày nhất nhận được sau kết quả làm việc của ban biên tập.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ (~1 \le k \le n \le 10^5~);
• Dòng thứ 2 chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^9, 1 \le i \le n~).

Output

• In ra màn hình số trang của tập dày nhất.

Sample Input 1

5 3
3 7 12 8 5

Sample Output 1

13

Trong buổi liên hoan chia tay, các bạn học sinh lớp 9A tổ chức một trò chơi như sau:

Có ~X~ cái kẹo rời bên ngoài và ~N~ hộp kẹo. Các hộp kẹo chứa các loại kẹo khác nhau, hộp kẹo thứ ~i~ có ~a_i~ cái kẹo (~0 \le a_i \le 1000~).

Trước tiên cán bộ lớp phát cho các bạn ~X~ cái kẹo rời bên ngoài. Sau đó, các bạn học sinh được chọn tùy ý các hộp kẹo trong ~N~ hộp kẹo đã cho sao cho tổng số cái kẹo của tất cả các bạn học sinh trong lớp 9A bằng đúng số ~Y~ cho trước. Vì muốn thưởng thức nhiều loại kẹo khác nhau nên các bạn tham gia trò chơi phải chọn sao cho số hộp kẹo là nhiều nhất có thể.

Yêu cầu: Hãy tính số lượng hộp kẹo nhiều nhất có thể lấy được, nếu không thể lấy được, kết quả là ~-1~.

Input

• Dòng đầu tiên chứa 3 số nguyên ~N~ (~0 < N \le 10^5~), ~X~, ~Y~ (~0 < X \le Y \le 10^3~), các số cách nhau một dấu cách.
• Dòng thứ hai chứa ~N~ số nguyên ~a_i~ (~0 \le a_i \le 1000~; ~1 \le i \le N~), các số cách nhau một dấu cách.

Output

• In ra màn hình số nguyên duy nhất là kết quả tính được.

Sample Input 1

5 2 10
1 2 3 4 5

Sample Output 1

3