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 đỏ. Mỗi bóng đèn đượ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:

  • Nếu đang tắt ~\rightarrow~ chuyển sang vàng.

  • Nếu đang vàng ~\rightarrow~ chuyển sang đỏ.

  • Nếu đang đỏ ~\rightarrow~ chuyển sang tắt.

• Khi xoay ngược chiều kim đồng hồ một nấc, trạng thái bóng đèn thay đổi:

  • Nếu đang tắt ~\rightarrow~ chuyển sang đỏ.

  • Nếu đang đỏ ~\rightarrow~ chuyển sang vàng.

  • Nếu đang vàng ~\rightarrow~ chuyển sang 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 \le L \le R \le N~. Cụ thể, mỗi yêu cầu 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ự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ó 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~ về trạng thái tắt.

Input

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

• Dòng đầu tiên chứa 4 số nguyên không âm ~N, Q, X, Y~ (~0 < X + Y \le 5~, ~X + Y \le N \le 666~, ~1 \le Q \le 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 \le i \le 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 \ge X + Y~ trong tất cả các yêu cầu.

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.

Scoring

Sample Input 1

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

Sample Output 1

3
2
-1

Notes

Yêu cầu của khảo sát đầu tiên cần ít nhất 3 thao tác. Hình sau minh họa 1 dãy thao tác tối ưu: