Under construction

Still being built. Things may change

Special Cake

Interview

Time limit1sMemory limit1024 MB

Summary
Given N statements about a cake thief, find every student who could be the culprit if all others tell the truth and the culprit lies on every statement.
Level

Medium4 of 10

Topics
Array, Implementation
Solved
No attempts yet

Problem

Waaah...

Someone took advantage of the darkness and ate Swi's huge cake again!

Swi, who loves cake as always, had put a huge cake bought from a nearby shop on the table and was admiring it. But the dormitory heater was so warm that Swi fell asleep, and the cake disappeared while Swi was asleep!

The person who ate the cake is either Swi or one of the NN students other than Swi who were in the dormitory at the time. To find the culprit, Swi questioned all NN students who were in the dormitory while Swi slept. Swi sorted each student's statement into one of the following two types.

  • Among the students in the list SS, the culprit is there.
  • Among the students in the list SS, the culprit is not there.

If one of the NN students is the culprit, every other student knows who it is, so every student except the culprit tells the truth, and the culprit lies to hide the fact of eating the cake. If none of the NN students is the culprit, then Swi ate the cake, so the truth of any statement cannot be determined.

Swi wants to narrow down the students who could be the culprit based on the NN statements. If assuming a student is the culprit creates no contradiction among the NN statements, that student is called a possible culprit. If none of the NN students is a possible culprit, then by elimination Swi is the culprit, so print swi.

Input

The first line contains the message that Swi's cake is missing, swi's cake is missing!.

The second line contains NN, the number of students who were in the dormitory other than Swi.

The next NN statements are given, each spanning three lines. The student who made the ii-th statement has number ii. Each statement has the following format.

  • The first line contains MM, the number of students in the list SS.
  • The second line contains the numbers of the students in the list SS, S1,S2,⋯ ,SMS_1,S_2,\cdots,S_M, separated by spaces with no repeats.
  • The third line contains an integer BB that indicates the type of statement. If the statement says the culprit is in the list, B=1B=1. If it says the culprit is not in the list, B=0B=0.

Output

Print the numbers of all possible culprits based on all the statements, in increasing order, separated by spaces.

If no student is a possible culprit, Swi ate the cake this time too, so print swi.

Constraints

  • 1≤N≤100 0001 \le N \le 100\,000
  • 1≤M≤N1 \le M \le N
  • 1≤Si≤N1 \le S_i \le N
  • The sum of the number of students in all lists does not exceed 200 000200\,000.

Examples3

  1. Example 1

    Input
    swi's cake is missing!
    2
    2
    1 2
    1
    2
    1 2
    1
    
    Expected output
    swi
    
  2. Example 2

    Input
    swi's cake is missing!
    2
    2
    1 2
    0
    1
    1
    1
    
    Expected output
    1
    
  3. Example 3

    Input
    swi's cake is missing!
    2
    1
    1
    0
    1
    2
    0
    
    Expected output
    1 2