Challenge 24 Electronic Contest Practice

In a prestigious but modern school teachers pay very much attention to being perfectly fair with their students. So they invented a complicated examination system in which each student has to turn in a finite series of non-negative integer numbers in place of the traditional, but very subjective essays. Every teacher who evaluates the works of the students has a so called evaluation function (an integer function with two arguments represented by f), a non-negative integer A and a positive integer B.

When a student hands in an exam (a sequence of integer numbers y₁, ... , y_N) the teacher evaluates it by applying the reduce operation to the sequence with the starting value A and operator f (the evaluation function). The result of the operation is the student's score. The student has passed the exam if this score is divisible by B.

The reduce operation is widely used in functional languages for calculating sums and products over sequences. In the case of evaluating the exams its result can be found by calculating x_N where

x₀ = A
x_i = f(x_i-1, y_i)

Note that students can also turn in an empty series (N = 0).

Because of a financial problem the director of the school decides to fire some of his teachers, but he wants to keep as much diversity in the school as possible. He holds that the essence of education is examination, so two teachers are different, if there is at least one such exam - that is a series of numbers - which they evaluate differently (i.e. one of them accepts it while the other rejects it). Your task is to find the equivalent teachers.

Input:

The first line of the input contains one integer, the number of teachers. Then two lines per teacher follows. The first line contains the numbers A and B. The second line contains a formula specifying the evaluation function. Each formula may contain parentheses, nonnegative integer numbers, operators +, - and * and the symbols x and y representing the first and the second argument respectively. The operator * has a higher precedence than operators + and -, but operators + and - have the same precedence. Their meaning is as usual.

Output:

Output exactly one line for each equivalence class of teachers. One class is specified by a space delimited list of numbers ordered incrementally. Each number identifies a teacher with his or her index in the input list. The first teacher is represented as 1. The classes have to be in increasing order of their first elements.

This is the electronic variant of the problem. Read more here about submitting solutions!

Example

Input:
4
0 10
(x+5)*(y+3)
1 10
x*y+5*y+3*x+15
0 10
x*x-y*y
0 10
x*y+5*y+3*x+15

Output:
1 4
2
3