Shopping Mall Design
Antoni is designing a new shopping mall! It is comprised of \(n\) cells numbered from \(1\) to \(n\) in a line. Of course, customers want to visit many different stores.
So, Matt has designed a transportation system to move people between the shops.
He thought of \(n-1\) positive integers \(a_1,...,a_n\) where for every \(i (1 \leq i \leq n-1)\) the condition \(1 \leq a_i \leq n-1\) holds.
Then, he made \(n-1\) tunnels numbered from \(1\) to \(n-1\). The \(i\)-th tunnel connects shop \(i\) and shop \((i+a_i)\). To keep the 'flow' of the shopping mall, constant one cannot travel backwards through a tunnel, only forwards. Trivially, since \(1 \leq a_i \leq n-1\) one cannot leave the mall once entering, genius!
At this point I should reveal I am stuck in this forsaken mall at cell \(1\) and want to go to cell \(t\) (they're having a really good sale). However, I don't know if I can get there, can you help me determine if I can reach cell \(t\) using the tunnel system?
Input Specification
Two lines. The first line contains two space-separated integers \(n (3 \leq n \leq 3 \times 10^4)\) and \(t (2\leq t \leq n)\); the number of shops and the index of the shop I want to get to.
The second line contains \(n-1\) space-separated integers \(a_1,...,a_{n-1} (1\leq a_i \leq n-1)\).
One is also guaranteed that using the tunnels, it is impossible to leave the shopping mall.
Output Specification
If I can get to the shop \(t\) using the tunnels print "YES". Otherwise, print "NO".
Sample Input 1
6 4
1 2 1 2 1 2
Sample Output 1
YES
Sample Input 2
8 5
1 2 1 2 1 1 1
Sample Output 2
NO
Note
In the first example, we visit the shops \(1,2,4\); so we can reach shop \(4\).
In the second example, we can only visit shops \(1,2,4,6,7,8\); so wee cannot visit shop \(5\).
Comments