MOZHCAN - Can Sharmeen Solve it? [ HARD ]

no tags 

Somehow Sharmeen solved the last problem “Sharmeen loves substring” and Mozahid became impressed on her performance. Now Mozahid wants to test her programming skill and gives her the hardest problem of today’s problem set. He will give her a string of lowercase English letters of size N( 1 <= N <= 10^5 ) and an integer X( 0 <= X <= 10^12 ). Sharmeen has to find the largest substring of that string, which has exactly X subsequences of ‘sms’. If multiple solution exists, she has to select the leftmost one. If no solution exists, she has to print “-1” (Without quotes); otherwise, she has to print the starting and ending position of the substring separated by a space in one line. For exact output format, see the Sample Input Output carefully.

 

N.B. Substring is a consecutive sequence of characters of a string, whereas subsequence does not necessarily need to be consecutive. But for both, you have to maintain the order. For clearance, ‘skmjssm’ has 2 different subsequences of ‘sms’.  {1,3,5} & {1,3,6} ( 1 based position ).

Input

In first line given test case T( 1 <= T <= 10 ).

For each test case, a string of lowercase English letters of size N( 1 <= N <= 10^5 ) and an integer X( 0 <= X <= 10^12 ) are given, separated by a space.

Output

For each test case, if solution exists, print the starting and ending position of the substring ( 1 based position ) separated by a space, otherwise print “-1” (without quote) in one line .

Example

Input:

2

smsmmsms 1

mmsm 1 Output:

1 5

-1

[ This problem originally written by MD. Mozahidul Islam Bhuiyan(kissu_pari_na) ]


hide comments
kaushalag29: 2018-07-04 16:29:33

@Avik Sarkar
Will the input string consists of only s and m or can have any lowercase english letters?

be1035016: 2018-07-03 13:26:25

good problem:)

amulyagaur: 2018-07-02 07:57:00

Fastest submission :) 0.08s

visleck: 2018-07-01 04:18:22

@avik can you tell me where exactly I am getting wrong. I have tested my solution against a brute force solution and it seems to pass all the cases.


Added by:Avik Sarkar
Date:2018-06-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own