MYQ2 - The Wild Wizard
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 |