Meltdown Deduction

You have invited n people (numbered from 0 to n-1) to play a game. They are seated in a circle so that person 0 and person n−1 are adjacent. Each person is given a card with a digit (either 0 or 1). Every player can see the cards of every person except for the two immediate neighbors; they can also see their own card.

The game is played in m rounds. In the i^th round, you announce k_i pieces of public information. Each piece of information is in the format:

“There exists at least one card with digit d in the set S.”

Here, S is a set of person indices and d is either 0 or 1. All players know the rules and are perfect logicians.

After the announcements in a round, each player tries to deduce the combined value of his two unknown neighbors' cards using only his own card, the cards he can see, and all the public announcements made up to that round. The functions to be deduced are defined as follows:

• If a player’s own card is 0, he must deduce the logical OR of his two neighbors’ cards. That is, if his neighbors hold values x and y, he needs to determine \(x \lor y\), where \(\lor\) is the OR operator. (Recall that \(0 \lor 0 = 0\) and any other combination yields 1.)
• If a player’s own card is 1, he must deduce the logical XOR of his two neighbors’ cards. That is, if his neighbors hold values x and y, he needs to determine \(x \oplus y\), where \(\oplus\) is the XOR operator. (Recall that \(0 \oplus 0 = 0\), \(1 \oplus 1 = 0\), and \(0 \oplus 1 = 1 \oplus 0 = 1\).)

If a player can deduce the required value (i.e. it is the same for all possibilities that are consistent with his private information and the public announcements) then he immediately shouts "Meltdown!" at the end of that round. All shouts occur simultaneously in the round in which the deduction becomes possible. Note that no additional inference is made after hearing others shout.

Your task is: Given the cards held by every player and all the announcements made over the rounds, determine for each person the first round in which he shouts "Meltdown!". If a person never shouts, output -1 for that person.

Deduction details

Before any announcements, each player sees every card except those of his two neighbors. In each round, new public information is provided. Each piece of information is of the form: "In the set S, there exists at least one card with digit d". For a given player with neighbor indices L and R, let V be the subset of S for which the card values are visible (i.e. S\{L,R}). If any card in V equals d, the claim is automatically satisfied. Otherwise, if S contains one or both of the unknown neighbors, then to satisfy the information, at least one of the unknown cards in S must equal d. The player uses all such constraints (from all rounds so far) to restrict the possible values of his two unknown neighbors. If under all possibilities the required function value (either \(x \lor y\) or \(x \oplus y\)) is the same, he can deduce that value.

inputFormat

The first line contains two integers n and m — the number of players and the number of rounds.

The second line contains a string of length n consisting of characters '0' and '1', where the i^th character denotes the card of player i.

The following describes the m rounds. For each round:

• The first line of the round contains an integer k, the number of announcements in that round.
• Then, for each announcement, there is a line beginning with an integer r (the size of the set S), followed by r distinct space‐separated integers representing the indices in S, and finally an integer d (either 0 or 1) indicating the digit.

Note: The rounds are cumulative. Announcements are retained in subsequent rounds.

outputFormat

Output a single line with n space-separated integers. The i^th integer should be the round number in which player i first shouts "Meltdown!". If player i never shouts, output -1 for that player.

sample

3 1
010
1
2 0 1 0

-1 -1 -1