All Tracks Algorithms Searching Binary Search Problem

The Substring Game!
Tag(s):

Algorithms, Binary Search, Implementation, Medium, Searching, Strings

Problem
Editorial
Analytics

Let's play the Substring Game.

This game has two characters: Sherlock and Watson. As usual, Watson wants to test the skills of Mr. Sherlock.

Watson gives Sherlock a string (let's denote it by S). Watson calculates all the substrings of S in his favourite order.

According to the Watson's favourite order, all the substrings starting from first character of the string will occur first in the sorted order of their length, followed by all the substrings starting from the second character of the string in the sorted order of their length, and so on.

For example:
Suppose the given string is "abc" that is S = abc. Then, all the substrings of S as per Watson's favourite order are:

1) a

2) ab

3) abc

4) b

5) bc

6) c

The game is pretty simple.

Watson will ask Sherlock 'q' questions. In each question, Watson will give Sherlock a number and Sherlock has to speak the substring on that number. If there is no possible substring, then Sherlock has to speak -1.

Note: Sherlock has to follow Watson's favourite order.

Help Sherlock.

See Sample test-case for more understanding.


Input format:

First line consist of a string 'S', having only the small alphabets (a - z).

Second Line consist of an integer 'q', number of questions Watson ask.

Next line consists of 'q' space-separated numbers.


Output format:

For all the 'q' questions, output the required answer, in a new line.


Constraints:

1 <= |S| <= 10^5

1 <= q <= 10^3

1 <= number <= 10^18

SAMPLE INPUT
abc
2
2 9
SAMPLE OUTPUT
ab
-1
Explanation

This is the example mentioned in the question.

In 1st case, Watson gives Sherlock a number 2. We have substring "ab" on number 2. So output "ab"(without quotes).

In 2nd case, Watson gives Sherlock a number 9. We don't have any substring on number 9. So output "-1" (without quotes).

Time Limit: 1.5 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...
Your Rating:

Contributor

This Problem was Asked in

ThoughtWorks

Challenge Name

ThoughtWorks Application Developer Hiring Challenge for Women

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?