Problem Description

One day, S decided to go on a drive on a circular road.

This circular road has rest stops at equal intervals, numbered from $0$ to $M - 1$. S starts at rest stop $0$ and drives in a loop: $0 → 1 → 2 → ... → (M - 2) → (M - 1) → 0 → 1 → 2 → ...$.

S's car can move one rest stop per liter of fuel. However, when refueling, S must choose one or more from $N$ fuel tanks with refueling amounts $a_1, a_2, a_3, ..., a_{N-1}, a_{N}$. Fuel tanks become empty after use, so the same tank cannot be chosen more than once. Since the car runs until it runs out of fuel, if S wants to stop at a specific rest stop, the fuel tanks must be chosen such that the fuel runs out exactly at that rest stop.

S has a meeting with a friend at rest stop number $L$. Starting with zero fuel, S wants to choose multiple fuel tanks to refuel and start at rest stop $0$ to stop at rest stop $L$. However, driving more than $X$ laps around the circular road violates city traffic regulations.

Determine if there is a way for S to choose fuel tanks such that S can stop at rest stop $L$ within $X$ laps.

Fuel can only be refilled once at the beginning. The start is defined as the first lap, and reaching rest stop $0$ again marks the start of the next lap.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ L $ $ X $ $ a_1 $ $ a_2 $ $ ... $ $ a_N $

The first line contains the number of fuel tanks $ N $, the number of rest stops $ M $, the target rest stop number $ L $, and the maximum allowed laps $ X $.

The second line contains the refueling amounts of the $ N $ fuel tanks, each given as a positive integer. $ a_i $ represents the refueling amount of the $ i $-th tank.

Output Format

Output "Yes" if S can stop at rest stop $ L $ within $ X $ laps, otherwise output "No".

Sample Input and Output

Sample Input #1

5 11 7 5
1 4 5 8 9

Sample Output #1

Yes

Sample Input #2

5 5 3 2
1 4 5 9 12

Sample Output #2

No

Sample Input #3

5 10 3 100
1 4 7 10 14

Sample Output #3

No

Notes/Hints

Constraints

• $ 1 ≤ N ≤ 10000 $
• $ 3 ≤ M ≤ 1000 $
• $ 1 ≤ L ≤ M - 1 $
• $ 2 ≤ X ≤ 10000 $
• $ 1 ≤ a_i ≤ 10000 $

Sample Explanation 1

It is not possible to make $ 7 $ (1st lap) by combining the numbers. $ 1 + 8 + 9 = 18 $, which equals 1 lap + target number ($ 11 + 7 = 18 $), so it is possible to stop at the 2nd lap ($ ≤ X = 5 $).

Sample Explanation 2

It is not possible to make $ 3 $ (1st lap), $ 8 $ (2nd lap) by combining the numbers. $ 1 + 12 = 13 $, which equals 2 laps + target number ($ 10 + 3 $), so it is possible to stop at the 3rd lap, but it exceeds $ X = 2 $ laps, so the answer is No.

Sample Explanation 3

No combination can make $ 3 $ (1st lap), $ 13 $ (2nd lap), $ 23 $ (3rd lap), $ 33 $ (4th lap).

见题面 Input 部分

见题面 Output 部分