M. Movieguessr
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

The year is $$$62442$$$ and Machado and Marcel were playing their favorite game, Movieguessr.

Movieguessr is a famous game that teleports its players into the universe of a movie, where they have a limited time to figure out which work they are in.

When Machado and Marcel thought it was just another round of the game, the unbelievable happened — the Movieguessr servers crashed, and they became trapped inside one of the most iconic schools from ancient movies, Hogwarts.

The two were on the famous magical staircase of Hogwarts, but in different positions on it, more specifically:

  • The staircase is represented by $$$N$$$ steps numbered from $$$1$$$ to $$$N$$$ and a list $$$a$$$ to represent them. The first step is at ground level $$$(a_1 = 0)$$$, and the rest can be above $$$(a_i = 1)$$$ or below $$$(a_i = -1)$$$ the previous step: going up a step increases a person's height by one unit; going down decreases it by one unit.
  • Marcel is on the $$$K$$$-th step.
  • Machado found a magic wand that allows him to teleport to any empty step on the staircase — that is, any step except the one Marcel is occupying.

Machado wants to use this magic to find his friend. Knowing that Machado can only see Marcel on the staircase if and only if his height is greater than or equal to Marcel's, and considering that Machado is $$$A$$$ units tall and Marcel is $$$B$$$, your mission is to help Machado: is there a step where Machado will be able to see Marcel? If so, to which step should he teleport in order to finally locate Marcel?

Input

The first line of the input contains $$$3$$$ integers $$$N$$$, $$$A$$$, and $$$B$$$ $$$(2 \le N \le 2 \cdot 10^5)$$$ $$$(1 \le A, B \le 10^9)$$$, the number of steps in the staircase, Machado's height, and Marcel's height, respectively.

The second line of the input contains $$$N$$$ integers $$$a_1, a_2, \cdots, a_N$$$, where $$$a_i$$$ is $$$1$$$ if the $$$i$$$-th step is above the previous one and $$$-1$$$ if it is below; also, $$$a_1 = 0$$$.

The third line of the input contains $$$1$$$ integer $$$K$$$ $$$(1 \le K \le N)$$$, the step Marcel is occupying.

Output

The first line of the output should contain "SIM" (without quotes) if there is a step where Machado can find Marcel, or "NAO" (without quotes) otherwise. If the answer is "SIM", the second line of the output should contain a number, the position Machado should teleport to in order to see Marcel; if more than one such step exists, any of them may be printed.

Examples
Input
5 10 8
0 1 -1 -1 1
2
Output
SIM
1
Input
11 2 4
0 1 1 -1 -1 -1 1 1 -1 1 -1
10
Output
NAO
Input
8 19 16
0 -1 1 1 1 1 1 1
8
Output
SIM
5