사면체

시간 제한2초메모리 제한256 MB

요약

막대기 여섯 개의 길이가 주어질 때, 각 막대기를 한 변씩으로 사용해 부피가 0이 아닌 사면체를 만들 수 있는지 판별한다.

난이도: 보통10점 중 4점
유형: 기하, 정렬, 수학, 그리디
정답자: 아직 제출이 없습니다

문제

"성냥은 아이들 장난감이 아니다"라는 속담이 있지만, 한 소년은 여전히 성냥을 가지고 노는 것을 아주 좋아한다. 그러나 성냥을 가지고 장난을 치거나 불을 붙이는 것이 아니라, 여러 가지 퍼즐을 푼다. 예를 들어, 성냥 하나만 옮겨서 숫자 9를 숫자 11과 같게 만들 수 있다.

최근에 이 소년의 부모님은 성냥 여섯 개로 이루어진 세트 여러 개를 선물해 주셨다. 소년은 그것들로 여러 가지 입체 도형을 만들기 시작했다. 이미 많은 도형을 만들었지만, 이제 궁금한 것이 생겼다. 어떤 세트에 들어 있는 성냥 여섯 개와 접착제로 부피가 0이 아닌 사면체의 골격을 붙일 수 있는가? 성냥을 부러뜨릴 수 없고, 어떤 성냥도 골격 밖으로 나와서는 안 된다.

여러분의 임무는 각 세트에 대해 주어진 성냥 길이를 이용해 그 성냥들로 사면체의 골격을 붙일 수 있는지 확인하는 것이다.

입력

첫째 줄에는 확인해야 하는 세트의 개수 $n$ ( $1 \le n \le 1000$ )이 주어진다. 그다음 $n$ 개의 줄에는 $i$ 번째 세트에 있는 성냥의 길이인 1 이상 1000 이하의 정수 여섯 개가 주어진다.

출력

$n$ 개의 줄을 출력한다. $i$ 번째 줄에는 $i$ 번째 세트로 부피가 0이 아닌 사면체를 만들 수 있으면 "Yes"를, 아니면 "No"를 출력한다.

예제1

예제 1

입력

4
1 1 1 1 1 1
1 2 3 1 2 3
1 2 1 2 1 2
1 2 2 1 2 2

예상 출력

Yes
No
Yes
Yes