АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Бүхэл тоон дараалал өгөгджээ. Энэ дараалалд бүхэл b₁ анхны гишүүн болон бүхэл q хуваарьтай байх геометр прогрессийн зарим гишүүнийг агуулдаг байг. Тэгвэл геометр прогрессын k дугаар гишүүнээс m дүгээр гишүүн хүртэлх гишүүдээс анх өгөгдсөн дараалалд хичнээн байгааг тодорхойлох програм бичнэ үү. Хэрэв шийд болох гишүүн хэд хэд байвал нэг гэж тооцно. Дарааллын гишүүдийн утга 2*10¹⁷-ээс хэтрэхгүй. Дарааллын r дүгээр гишүүнийг b_r=b₁*q^{n-1 томьёогоор олно. Давтагдсан гишүүнийг нэг байгаагаар авна.}  

Input

Эхний мөрөнд дарааллын гишүүний тоо N<=100000 ба 1<=b₁<=32000, 2<=q<=100 байх тоонууд сул зайгаар тусгаарлагдан өгөгдөнө. Дараагийн мөрөнд k ба m тоонууд (1<=k<m<=100) өгөгдөнө. Гуравдугаар мөрөнд N ширхэг тоо сул зайгаар тусгаарлагдан өгөгдөнө.

Output

Геометр прогрессын дараалсан хамгийн олон гишүүдийн тоог агуулна.

Example

Input 1:

10 1 2

1 5

1 7 2 3 16 4 9 8 11 10

Output 1:

5

Input 2:

15 5 3

2 10

10935 1 135 52 3 8 15 45 20 3645 9 8 1215 89 225 

Output 2:

6