MYQ2 - The Wild Wizard

no tags 


In the country of Thuvax lived an old wizard named Chanithpra. He practised a form of magic in which the power of spell came from the letters that were written on a piece of parchment.
When a sentence s is written, the intensity of the letters are as follows:
1. Intensity of 'a' is 1, 'b' is 2 and it continues till 'z' whose intensity is 26.
2. Intensity of 'A' is 51, 'B' is 52 and it continues till 'Z' whose intensity is 76.
3. Intensity of ' '(space) is 32.
 
The power of a spell written as a part of the sentence is equal to the sum of the intensities of the characters present in it modulo m.
 
Chanithpra finds an old parchment in Thuvax with a sentence s written on it.
Help him find the longest spell (i, i+1, ... j) in the sentence s whose power matches with k. (0<=i<=j<length of s)
 
You need to print the starting index i(0<=i<=length-1) of such a spell in the sentence and the length of the spell.  
 
If there are multiple such spells, find the minumum index i and if there is no such spell print -1.

Input

The first line contains a single positive integer t(1<=t<=100) denoting the number of test cases.
Each test case consists of 2 lines:
The first line consists of the sentence s(1<=length of s<=1000000).
The second line consists of two integers m and k (2<=m<=1000007 and 0<=k<m).

Output

For each test case, output one line containing 2 integers. The first is the minimum index i(0<=i<=s.length-1). The second is the length of the spell.
If no such spell is present, print -1

Example

Input:
1
Hello World
10 7 Output: 0 7

hide comments
Shivam: 2013-12-12 02:40:22

does input contain any other characters than the english alphabet and spaces ?

Venkatesh Ganesan: 2013-11-07 19:34:13

8 WAs -> All due to scanning of input. :P

Vikas Kushwaha: 2013-07-29 13:35:57

got so many WA because of error in scanning the input.. finally AC :)

Mahavir Chopra: 2013-01-13 12:19:22

some test cases plss..!!!!

BlackBird: 2012-09-01 08:36:26

Just to help others: Scanning the input is a more difficult challenge than the algorithm :)

Gurpreet Singh: 2012-07-01 07:08:27

Is it that the sentence 's' can begin and/or end with spaces. Also, can there be a case when the sentence 's' contains only spaces ?


Added by:jack(chakradarraju)
Date:2012-02-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Bytecode 2012