MOZHCAN  Can Sharmeen Solve it? [ HARD ]
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:
20180704 16:29:33
@Avik Sarkar


be1035016:
20180703 13:26:25
good problem:) 

amulyagaur:
20180702 07:57:00
Fastest submission :) 0.08s 

visleck:
20180701 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:  20180622 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Own 