問題文

ある日 S 君は環状の道路をドライブすることにした。

この環状道路には等間隔に休憩所があり、0 から M - 1 までの番号が振られている。
S 君は0番の休憩所からスタートし、0 → 1 → 2 → … → (M - 2) → (M - 1) → 0 → 1 → 2 → … と巡回する。

S 君の車は，燃料1リットルで休憩所を1つ進むことができる。
しかし燃料の補充の際は、あらかじめ用意した、補充量が a_1 , a_2 , a_3 ,…, a_{N-1} , a_{N} である N 個の燃料タンクから 1 つ以上選んで補充しなけらばならない。
燃料タンクは補充を行うと空になるため、同じ燃料タンクを2回以上選ぶことはできない。 この車は走り出すと燃料を使い切るまで止まらないため、ある特定の休憩所に停まりたい場合は、ぴったりそこで燃料が尽きるように補充する燃料タンクを選ばなければならない。

S 君は番号Lの休憩所で友人と待ち合わせをしており、車の燃料が0の状態で燃料タンクを複数選んで補充し、番号0の休憩所からスタートして番号Lの休憩所に停まりたい。
しかし環状道路をX周以上すると市の交通条例違反になってしまう。

S 君がX周以内に番号Lの休憩所に停まることができるような燃料タンクの選び方は存在するかどうかを判定せよ。

燃料の補充は最初の1回のみである。また、スタート直後は1周目と定義し、再び番号0の休憩所にたどり着いた時点で次の周回とする。

制約

• 1 \leq N \leq 10000
• 3 \leq M \leq 1000
• 1 \leq L \leq M - 1
• 2 \leq X \leq 10000
• 1 \leq a_i \leq 10000