피자 드실 분?

시간 제한1초메모리 제한128 MB

요약

각 친구는 자신의 요청 중 하나라도 충족하면 만족한다. 토핑 수가 가장 적고, 그중 사전순으로 가장 작은 피자를 찾고, 없으면 불가능을 출력한다.

난이도: 보통10점 중 6점
유형: 비트 연산, 완전 탐색, 구현, 그리디
정답자: 아직 제출이 없습니다

문제

당신은 친구들과 함께 먹을 라지 피자 한 판을 주문하려고 합니다. 친구들은 저마다 피자에 넣고 싶은 것과 넣기 싫은 것을 말해 주었습니다. 그런데 피자는 단 한 판뿐이라, 모든 요구를 다 들어주기는 어렵습니다. 목표는 모든 친구의 요구 중 적어도 하나를 만족시키는 피자 한 판을 주문하는 것입니다.

피자 가게에서 고를 수 있는 토핑은 다음과 같으며, 각 토핑을 넣을지 뺄지는 자유롭게 정할 수 있습니다.

입력 코드	토핑
A	앤초비
B	블랙 올리브
C	캐나디안 베이컨
D	다진 마늘
E	추가 치즈
F	생 브로콜리
G	피망
H	햄
I	이탈리안 소시지
J	할라피뇨
K	킬바사(폴란드 소시지)
L	다진 살코기 소고기
M	버섯
N	무지방 페타 치즈
O	양파
P	페퍼로니

각 친구는 자신의 취향을 요청 목록 형태로 한 줄에 적어 줍니다. 요청 +X는 "피자에 토핑 X가 있어야 한다", 요청 -X는 "피자에 토핑 X가 없어야 한다"를 뜻합니다. 어떤 친구는 자신의 요청 중 하나라도 충족되면 만족합니다. 예를 들어 +O-H+P;는 피자에 양파가 있거나, 또는 햄이 없거나, 또는 페퍼로니가 있으면 만족하는 친구를 나타냅니다.

입력

입력은 하나 이상의 피자 케이스로 이루어집니다.

하나의 피자 케이스는 친구 1명부터 12명까지의 줄(한 줄에 친구 한 명)로 구성되며, 그 뒤에 마침표 . 하나만 있는 줄이 옵니다.

각 친구 줄은 세미콜론 ; 하나로 끝나는 요청들의 나열입니다. 각 요청은 부호 문자(+ 또는 -) 바로 뒤에 대문자 토핑 코드 A부터 P까지가 붙은 형태입니다. 한 줄 안에서 같은 토핑 코드가 여러 번 나올 수도 있습니다. 케이스 내부에 빈 줄은 없으며, 입력은 파일 끝에서 종료됩니다.

출력

각 피자 케이스마다 정확히 한 줄을 출력합니다.

모든 친구를 만족시키는 피자가 하나라도 있으면, 그런 피자는 여러 개일 수 있습니다. 그중 토핑 개수가 가장 적은 피자를 고르고, 토핑 개수가 같아 여러 개라면 토핑 목록이 사전순으로 가장 앞서는 피자를 고릅니다. Toppings: 다음에 고른 토핑들을 대문자로 알파벳 순서대로 이어서 출력합니다. 고른 피자에 토핑이 하나도 없으면 뒤에 아무것도 붙이지 않고 정확히 Toppings:만 출력합니다. 예를 들어 앤초비, 햄, 다진 살코기 소고기, 페퍼로니가 올라간 피자는 Toppings: AHLP로 출력됩니다.

모든 친구를 만족시키는 피자가 하나도 없으면, 다음을 정확히 출력합니다.

No pizza can satisfy these requests.

예제2

예제 1

입력

+A+B+C+D-E-F-G-H;
-A-B+C+D-E-F+G+H;
-A+B-C+D-E+F-G+H;
.
+A+B+C+D;
+E+F+F+H;
+A+B-G;
+O+J-F;
+H+I+C;
+P;
+O+M+L;
+M-L+P;
.
+A+B+C+D;
+E+F+F+H;
+A+B-G;
+P-O;
+O+J-F;
+H+I+C;
+P;
+O;
+O+M+L;
-O-P;
+M-L+P;
.

예상 출력

Toppings:
Toppings: AHLP
No pizza can satisfy these requests.

예제 2
입력
```
+A+B;
-A;
.
```
예상 출력
```
Toppings: B
```