Sewer Extermination Simulation

In the sewer system, exterminators are fighting a rapidly reproducing mouse population using a series of weapon deployments and interventions. Although the original story involves complex movements and various weapons, this simplified simulation focuses on the overall mouse population dynamics.

Initially, there are M mice. The extermination plan lasts for T time steps. At each time step i (with 1 ≤ i ≤ T), the mouse population changes by an integer amount given in the input. This change can be positive (due to reproduction) or negative (due to extermination by weapons). The changes are applied sequentially.

Your task is to simulate the process and determine whether, at any time step, the number of mice exceeds a given threshold K. In mathematical terms, if after applying the change at some time step the new population count satisfies $$count > K,$$ then a plague outbreak will occur. Report the first time step when this happens.

If the mouse population never exceeds K during the simulation, output safe.

inputFormat

The first line of input contains three space-separated integers: T (the number of time steps), M (the initial number of mice), and K (the outbreak threshold).

The second line contains T space-separated integers, where the i-th integer represents the net change in the mouse population at the i-th time step.

Note: The net change can be negative or positive.

outputFormat

If at any time step the number of mice becomes greater than K (i.e. if count > K), output the 1-indexed time step when the outbreak first occurs. Otherwise, output safe if no outbreak occurs during the simulation.

sample

5 10 50
5 10 -3 20 5

safe