피자 토핑 정하기

친구들과 큰 피자 한 판을 시켜서 나눠 먹기로 했다. 각자 올리고 싶은 것이 달라서 토핑을 고르는 일이 만만치 않다. 구나르는 바나나를 올리자고 하고, 엠마는 바나나는 빼고 올리브를 올리자고 하고, 마르크는 토마토를 꼭 넣자고 한다.

예전에 한 번은 모두의 희망 사항을 2/3 이상 만족시키는 토핑 조합을 겨우 찾아냈고, 그 정도면 충분하다고 다들 동의했다. 그런데 피자를 사러 가던 루카스가 그 목록을 적은 종이를 잃어버렸다. 처음부터 다시 골라야 해서 기준을 낮추기로 했다. 이번에는 모든 친구가 자기 희망 사항의 1/3보다 많이 만족하는 토핑 조합을 찾는다.

첫째 줄에 친구 수 $N$ ($1 \le N \le 10000$)이 주어진다. 나도 이 수에 포함된다. 다음 $N$개 줄에는 친구 한 명의 희망 사항이 한 줄씩 주어진다. 각 줄은 그 친구의 희망 사항 개수 $w$ ($1 \le w \le 30$)로 시작하고, 이어서 희망 사항 $w$개가 공백으로 구분되어 주어진다. 희망 사항은 +토핑 또는 -토핑 꼴로 적혀 있다. +토핑은 그 토핑을 피자에 올려 달라는 뜻이고, -토핑은 그 토핑을 올리지 말아 달라는 뜻이다. 한 줄 안에서 같은 토핑 이름은 두 번 나오지 않는다.

토핑 이름은 알파벳 소문자로만 이루어진 길이 15 이하의 문자열이다. 입력에 나오는 서로 다른 토핑은 250개 이하이다.

+토핑이 가리키는 토핑이 피자에 올라가 있으면 그 희망 사항을 만족한 것이고, -토핑이 가리키는 토핑이 피자에 없으면 그 희망 사항을 만족한 것이다. 희망 사항이 $w$개인 친구가 그중 $f$개를 만족했을 때, $3f > w$이면 그 친구는 만족한다.

모든 친구가 만족하는 토핑 조합을 출력한다. 모든 친구의 희망 사항을 2/3 이상 만족시키는 토핑 조합이 존재한다고 가정해도 좋다. 조건을 만족하는 조합은 여러 개일 수 있으므로, 아래 절차가 만드는 조합을 그대로 출력한다.

친구에게 입력 순서대로 1번부터 $N$번까지 번호를 매긴다. 피자에 토핑을 하나도 올리지 않은 상태에서 시작하고 $r = 1$로 둔 다음, 아래를 반복한다.

1. 모든 친구가 만족하면 절차를 끝낸다.
2. 그렇지 않으면 만족하지 않는 친구 중 번호가 가장 작은 친구를 $i$라 하자. 친구 $i$의 희망 사항 중 아직 만족하지 않은 것을 토핑 이름의 사전순으로 나열한 목록을 $L$, 그 길이를 $u$라 하자.
3. $r$를 $(48271 \times r) \bmod 2147483647$로 바꾸고 $k = r \bmod u$로 둔다.
4. $L$에서 0번부터 세어 $k$번째에 있는 희망 사항을 만족시킨다. 그 희망 사항이 +이면 해당 토핑을 피자에 올리고, -이면 피자에서 뺀다.

절차가 끝나면 피자에 올라가 있는 토핑을 사전순으로 한 줄에 하나씩 출력한다. 출력하는 토핑은 모두 입력에 나온 토핑이고, 같은 토핑을 두 번 출력하지 않는다.