Magical Walk
Tag(s):

Problem
Editorial
Analytics

Pranay went for a walk around a circular park. the park has K entry/exit points and one can enter/exit from any of them. But the gates of park have a specific crossing charges if one has money greater than crossing charge he can cross that gate. Pranay has a fixed amount of money M and he enters the park from a gate S. As Pranay is weak with numbers, help him calculate the gate from which he exits keeping in mind the fixed amount of money he has. If Pranay cannot pass a gate then he must exit from that gate only. If Pranay cannot enter the starting gate due to shortage of money print -1. Pranay will keep on walking till he can. Indexing is 1 based.

Input :

First line consists of a single integer T, number of test cases.

For each test case :

First line of input contains an integer K specifying number of gates in the park.

Second line contains K seperate integers specifying crossing charges for each gate.

Third line contains an integer S specifying gate from which Pranay enters.

Fourth line contains an integer M specifying amount of money Pranay has.

Fifth line consists of a single integer D telling the direction in which Pranay will move, 1 for clockwise and -1 for anti clockwise

Output

Print an integer X specifying gate number from which Pranay exits.

Constraints :

1 <= T <= 100

1 <= S <= K <= 1000

1 <= M <=1000000000

1 <= Charge of passing at any gate <=1000000000

SAMPLE INPUT
1
5
2 4 3 5 7
1
10
1
SAMPLE OUTPUT
4
Explanation

Pranay has 10 Rs initially, he starts at gate number 1, and to pass through gate number 1 he pays a charge of 2 Rs. Now Pranay has 8 Rs left, to pass through gate number 2 he pays a charge of 4 Rs, and is left with 4 Rs. He passes gate 3 by paying 3 Rs. Now he has 1 Rs left,and is at gate number 4 but he cannot pass through gate number 4. So Pranay will exit through gate number 4.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

Codester Novice Prelims

OTHER PROBLEMS OF THIS CHALLENGE
• Data Structures > Stacks