좀비 제비

영화 『몬티 파이썬과 성배』에는 “짐을 싣지 않은 제비의 비행 속도는 얼마인가?”라는 유명한 질문을 둘러싼 장면이 있다. 언데드 조류학자에게 더 중요한 질문은 아마도 “좀비 제비가 삼킬 수 있는 곤충의 양은 얼마인가?”일 것이다.

좀비 제비를 다루려면 그 제비가 무엇을 삼키는지를 통제해야 한다. 무덤에서 막 일어난 좀비 제비의 위(胃)는 비어 있으므로 즉시 먹이를 주어야 한다. 각 좀비 제비는 최소 에너지 요구량은 반드시 채워야 하지만, 위 용량을 초과해서 삼켜서는 안 된다. 즉, 먹을 수 있는 곤충들이 주어졌을 때, 제비는 삼킨 곤충 무게의 합이 최소 요구량 $C_{min}$ 마이크로그램 이상이면서 위 용량 $C_{max}$ 마이크로그램 이하가 되도록 곤충의 부분집합을 골라 삼킨다. 이런 조건을 만족하는 조합이 존재하면 그 제비는 살아남는다.

각 제비에 대해, 고를 수 있는 곤충들 중 일부(부분집합)를 선택하여 그 무게의 합을 $C_{min}$ 이상 $C_{max}$ 이하로 만들 수 있는지 판정하여라. (아무 곤충도 삼키지 않는 빈 부분집합도 허용되며, 이때 합은 $0$이다.)

첫째 줄에 곤충을 삼켜야 하는 제비의 수 $S$ ($S \le 30$)가 주어진다. 이어서 $S$개의 줄에 걸쳐 각 제비의 먹이 정보가 한 줄씩 주어진다. 각 줄은 다음과 같이 구성된다.

• 두 정수 $C_{min}$, $C_{max}$ ($0 \le C_{min} < C_{max} \le 2^{26}$): 각각 그 제비의 최소 에너지 요구량과 최대 위 용량(마이크로그램).
• 정수 $n$ ($0 \le n \le 150$): 그 제비가 고를 수 있는 곤충의 수.
• 이어서 $n$개의 정수: 각 곤충의 무게(마이크로그램)로, 모두 양의 정수이며 $2^{26}$ 이하이다.

좀비 제비의 특성상 $1 \le \dfrac{C_{max}}{C_{max} - C_{min}} \le 60000$ 이 항상 성립한다.

각 제비에 대해, 먹이 조건을 만족시킬 수 있으면 Sallow swallow swallows. 를 출력한다. 어떤 곤충 조합으로도 조건을 만족시킬 수 없으면(무엇을 고르든 부족하거나 초과하게 되면) Sallow swallow wallows in dust. 를 출력한다. 결과는 입력에 주어진 제비 순서대로 출력한다.