There are N toilets around Duck, each of them will begin to release O_i units of odors after i units of time. For example, there are three toilets producing 20, 10, 15 units of odors respectively. The first toilet will immediately release smells, the second one will release smells after 1 seconds and the third is after 2 seconds. So at the time 1, the total amount of released odors is 20 * 1 = 20, at time 2 is 20 * 2 + 10 * 1 = 50 and at time 3 is 20 * 3 + 10 * 2 + 15 * 1 =  95. Duck can only go to toilet when the absolute difference between the total amount of released odors at a certain time and his tolerance to odors M is minimized. Please find out at what time the difference is minimized. If there are two answers, choose the larger time.

After that, Duck will enter one of the toilets randomly. Given a string S, Duck knows which cubicles are available and which are occupied, 'x' means occupied and 'o' means available. Let the time that minimizes the difference be ANS, and the smallest power of 10 that equal or larger than ANS be P. Assuming the toilet entrance is located at the position floor(ANS / P * (len(S) - 1)) of S, that is, the cubicle at that position is replaced by the entrance. You are required to select the best cubicle for Duck: available, maximizes the total distance between the nearest occupied cubicle on the left and right side as possible and it should be in the middle between the left nearest and right nearest occupied cuicle as possible (if no occupied cubicles next to the chosen range, you may assume there is an occupied cubicle on the most left and most right side and the entrance is also an occupied cubicle), and then as close to the entrance as possible. If there is more than one best choice, select the one on the right side of the entrance because Duck is always right. Please help him, he wants to excrete comfortably.

Input

The first line is the number of test cases T. (1 ≤ T ≤ 50)

For each test case, it starts with two integers N (Number of toilets) and M (Duck's tolerance to odors). (1 ≤ N ≤ 500, N ≤ M ≤ 10¹⁸)

The next line is a string S consisting of 'x' and 'o', representing the status of cubicles (3 ≤ |S| ≤ 100)

Following N lines are the O_i units of odors released by i th toilet (1 ≤ O_i ≤ 10⁵)

It is guaranteed that in S, 'o' will appear at least twice, so the answer always exists.

Output

Print two integers in format 'x y' without quotes, where x is the time minimizes the absolute difference between the total amount of released odors at a certain time and M, y is the position of best cubicle counting from 0

Example

Input:
2
2

4 78
ooxoxxoooxxxxxooooxoooo
2
13
1
5

5 35
xxoooxoooxx
1
2
3
4
5
5
Output:
5 15
5 7

Explanation

In case one, the time is 5 because 2 * 5 + 13 * 4 + 1 * 3 + 5 * 2 = 75 minimizes the difference between it and 78. The length of S is 23, so the entrance is at position floor(5 / 10 * 22) = 11, and S becomes 'ooxoxxoooxxExxooooxoooo', and we can see that the cubicle at position 15 is available, as far away from the nearest occupied cubicles as possible, and as close to the entrance as possible.

In case two, at time 5, the minimized difference is 0. So S becomes 'xxoooEoooxx'. There are two best cubicles: position 3 and 7, and we choose the right one, so the answer is 7.