Need helping with the following java program:

Alice is very fond of water fowl, and has invited Bob to play her favorite game. In the game Alice has arranged ten water fowl in row in the next room, and Bob is allowed ask a series of questions about this arrangement.

Bob's questions follow one of the following templates:

He can ask about a particular bird:

"Is the third bird a duck?"

"Is the first bird a goose?"

He can also also about total number of birds of any type:

"Are there 2 ducks?"

"Are there 3 geese?"

He can combine questions of types 1 and 2 with logical or's or and's. Multiple logical operators can be used in a question, however, they must all be of the same type. In other words, there will be no questions that use both or and and. Example questions could be:

"Is the first bird a duck or the second bird a goose?"

"Is the ninth bird a swan and are there two geese and is the second bird a duck?"

Unfortunately, Alice is very dishonest, so the game has become a bit more difficult than it should be. Fortunately, Alice is upfront about her dishonesty. At the start of each game, Alice tells Bob how many lies she will tell. She will be honest about the number of lies.

Your task is to help Bob figure out what the sequence of waterfowl could be, given Alice's responses.

Input Format

The input begins an integer g, which gives the number of games that are played.

Each game begins with a blank line. Then there is a line containing two integers q and n, with q equal to the number of questions Bob asked, and n being the number of dishonest answers Alice gave to Bob's questions.

Next come q pairs of lines, with a question on the first line and an answer on the second. The questions will be made up of clauses in the following form:

bird i t total t j 

The first question is equivalent to "Is the ith bird a t?" where i is an integer, and t will be a single character: 'd' for duck, 'g' for goose, or 's' for swan.

The second question is equivalent to "Is the total number of t equal to j?", where t is a character as in the first type of question, and j is an integer.

Questions of the forms above can be combined with logical operators.

The answer, given by Alice, will be a yes or no, and appear on the line immediately after the question.

Constraints

1 g 20

1 q 20, 0 n q

1 i 10

0 j 10

There will be at most 9 logical operators in a question.

Output Format

For each game, please output a line containing space-separated values. The nth value should be the possible types of waterfowl for the nth bird. Choose the appropriate values from the list below:

d, if the bird must be a duck.

g, if the bird must be a goose.

s, if the bird must be a swan.

dg, if the bird cannot be a swan.

ds, if the bird cannot be a goose.

gs, if the bird cannot be a duck.

dgs, if the bird could be a duck, goose, or a swan.

Sample Input 0

3 2 2 bird 1 s yes bird 2 d no 3 1 total d 4 and total g 7 yes bird 1 s and bird 2 d and bird 3 s yes bird 1 g or bird 4 g yes 2 0 total d 1 yes bird 6 s or bird 1 d yes 

Sample Output 0

dg d dgs dgs dgs dgs dgs dgs dgs dgs s d s g dgs dgs dgs dgs dgs dgs dgs dgs dgs dgs dgs gs dgs dgs dgs dgs 

Explanation 0

Game 1

Bob asks two questions in the first game, and Alices lies in both her responses.

Since Alice said that the first bird is a swan, and she lied, you know that it cannot be a swan, and you should output dg.

Alice said that the second bird is not a duck, and shed lied. Thus, you know that the bird must be a duck, and you should output d.

Game 2

In the second game, Alice told the truth twice, and lied once.

Bob starts by asking "Are there 4 ducks and 7 geese?" Alice says yes. However, there are only 10 birds, and a bird cannot simultaneously be a duck and a goose. Thus, you can conclude that this answer is a lie, and Alice's remaining answers are the truth.

Bob then asks "Is the first bird a swan, the second bird a duck, and the third bird a swan?" Since the answer is "yes", and it is truthful, you know the types of the first 3 birds.

Bob's last question is: "Is the first bird a goose or the fourth bird a goose?" Since Alice truthfully answers "yes", and you know that the first bird is a swan, you can conclude that the fourth bird must be a goose.

Game 3

Alice answers truthfully in the last game. We know that

There is one duck.

Either the sixth bird is a swan, or the first bird is a duck, or both.

Note that if the first bird is a duck, there can be no other ducks. If the first bird is not a duck, then the sixth bird must be a swan. Therefore, the sixth bird can never be a duck!