Giáng sinh năm nay, khu phố VOI được trang trí bởi một dàn ~N~ bóng đèn, các bóng đèn được đánh số từ ~1~ đến ~N~. Ban đầu, mỗi bóng đèn ở một trong ~3~ trạng thái tắt, vàng hoặc đỏ và được điều khiển bởi một công tắc vòng tròn hoạt động như sau:

• Khi xoay theo chiều kim đồng hồ một nấc, trạng thái bóng đèn đó thay đổi theo quy tắc:
  • Nếu đang ở trạng thái tắt thì chuyển sang trạng thái vàng.
  • Nếu đang ở trạng thái vàng thì chuyển sang trạng thái đỏ.
  • Nếu đang ở trạng thái đỏ thì chuyển sang trạng thái tắt.
• Khi xoay ngược chiều kim đồng hồ một nấc, trạng thái bóng đèn đó thay đổi theo quy tắc:
  • Nếu đang ở trạng thái tắt thì chuyển sang trạng thái đỏ.
  • Nếu đang ở trạng thái đỏ thì chuyển sang trạng thái vàng.
  • Nếu đang ở trạng thái vàng thì chuyển sang trạng thái tắt.

Ban quản trị VOI nhận được ~Q~ yêu cầu khảo sát, mỗi yêu cầu gồm hai giá trị ~L~ và ~R~ với ~1 ≤ L ≤ R ≤ N~. Cụ thể, mỗi yêu cầu khảo sát cần tìm một dãy các thao tác để đưa tất cả các bóng đèn từ ~L~ đến ~R~ về trạng thái tắt, mỗi thao tác có thể thực hiện như sau:

Chọn ~X + Y~ bóng đèn phân biệt trong đoạn từ ~L~ đến ~R~, trong đó: ~X~ bóng đèn để xoay công tắc theo chiều kim đồng hồ một nấc, ~Y~ bóng đèn còn lại để xoay công tắc ngược chiều kim đồng hồ một nấc.

Lưu ý: Các yêu cầu khảo sát là độc lập, nghĩa là mỗi yêu cầu đều được xử lý trên trạng thái ban đầu của dãy đèn. Giá trị ~X~ và ~Y~ cố định cho tất cả ~Q~ yêu cầu. Các công tắc vòng tròn được thiết kế để có thể xoay không giới hạn theo cả hai chiều.

Yêu cầu: Với mỗi yêu cầu khảo sát, hãy tìm số thao tác ít nhất để đưa toàn bộ các bóng đèn trong đoạn từ L đến R của dãy đèn về trạng thái tắt.

Input

Vào từ file văn bản LIGHT.INP:

• Dòng đầu chứa ~4~ số nguyên không âm ~N, Q, X, Y~ (~0 < X + Y ≤ 5~, ~X + Y ≤ N ≤ 666~, ~1 ≤ Q ≤ 10^5~).
• Dòng thứ hai chứa ~N~ số nguyên, số thứ ~i~ có giá trị ~0, 1~ hoặc ~2~ tương ứng với trạng thái ban đầu của bóng đèn thứ ~i~ là tắt, vàng hoặc đỏ (~1 ≤ i ≤ N~).
• Mỗi dòng trong số ~Q~ dòng tiếp theo chứa hai số nguyên dương ~L~ và ~R~ mô tả một yêu cầu. Dữ liệu bảo đảm ~R - L + 1 ≥ X + Y~ trong tất cả các yêu cầu khảo sát.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

Ghi ra file văn bản LIGHT.OUT:

• Gồm ~Q~ dòng, mỗi dòng một số nguyên là số lượng thao tác ít nhất tìm được cho yêu cầu khảo sát tương ứng hoặc ~-1~ nếu không tồn tại phương án.

Sample Input

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

Sample Output

3
2
-1

Yêu cầu khảo sát đầu tiên cần ít nhất ~3~ thao tác. Hình sau minh hoạ một dãy thao tác tối ưu:

Subtasks