Jump to content
Sign in to follow this  
Warrior

Problema: The Wild Wizard

Recommended Posts

Warrior

Acho que está na altura de colocar um novo problema dado que o último problema foi colocado há uma semana.

Link: 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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.