The trilero of la Rambla P61627


Statement
 

pdf   zip

thehtml

One day, walking down la Rambla of Barcelona, you notice a crowd around a board table. You get closer and you see that a “trilero” (someone who makes a living by cheating people) is ‍playing a game with a tourist.

The game is as follows. On the table there are n identical plastic caps. First, the trilero hides a ball under one of the caps, initially known to the player. Then the trilero starts moving the caps very fast. At the end, the player must guess under which cap the ball is.

The game is over and, obviously, the tourist has lost it (and some money). But you realize that the trilero just repeats k times the same permutation of caps σ. This is why he can be so fast! Please write a program that, given σ, k and the initial position x of the ball, tells the final position of the ball.

Input

Input consists of several cases. Every case begins with n, followed by a permutation of the numbers between 1 and n, followed by k and x. Assume 1 ≤ n ≤ 105, 1 ≤ k ≤ 109, and 1 ≤ x ≤ n.

Output

For every case, print the final position of the ball.

Public test cases

  • Input

    4  2 3 4 1
1 3

3  1 3 2
2 3

3  1 3 2
10 1

10  5 4 8 9 1 6 3 2 7 10
5 2

10  5 4 8 9 1 6 3 2 7 10
12000005 2

    Output

    4
3
1
8
8
    • Information
    Author
    Enric Rodríguez
    Language
    English
    Official solutions
    C++
    User solutions
    C++