Welcome To SDIBT ACM-ICPC Online Judge

VIRTUAL JUDGE Recent Contest F.A.Qs Forum Home ProblemSet Status Ranklist Contest LoginRegister Exam
Problem 1069. -- Repackaging


Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 0  Solved: 0


Coffee cups of three different sizes (size 1, size 2, and size 3) are manufactured by the Association of Cup Makers (ACM) and are sold in various packages. Each type of package is identified by three positive integers ( S1, S2, S3), where Si ( 1,=i<=3) denotes the number of size i cups included in the package. Unfortunately, there is no package such that S1 = S2 = S3. Market research has discovered there is great demand for packages containing equal numbers of cups of all three sizes. To exploit this opportunity, ACM has decided to unpack the cups from some of the packages in its unlimited stock of unsold products and repack them as packages having equal number of cups of all three sizes. For example, suppose ACM has the following packages in its stock: (1, 2, 3), (1, 11, 5), (9, 4, 3), and (2, 3, 2). Then we can unpack three (1, 2, 3) packages, one (9, 4, 3) package, and two (2, 3, 2) packages and repack the cups to produce sixteen (1, 1, 1) packages. One can even produce eight (2, 2, 2) packages or four (4, 4, 4) packages or two (8, 8, 8) packages or one (16, 16, 16) package, etc. Note that all the unpacked cups must be used to produce the new packages; i.e., no unpacked cup is wasted. ACM has hired you to write a program to decide whether it is possible to produce packages containing an equal number of all three types of cups using all the cups that can be found by unpacking any combination of existing packages in stock


The input may contain multiple test cases. Each test case begins with a line containing an integer N ( 3N 1,000) indicating the number of different types of packages that can be found in the stock. Each of the next N lines contains three positive integers denoting, respectively, the number of size 1, size 2, and size 3 cups in a package. No two packages in a test case will have the same specification. A test case containing a zero for N in the first line terminates the input.


For each test case print a line containing ``Yes'' if packages can be produced as desired. Print ``No'' if they cannot be produced.

Sample Input

1 2 3
1 11 5
9 4 3
2 3 2
1 3 3
1 11 5
9 4 3
2 3 2

Sample Output






한국어 中文 English
All Copyright Reserved 2008-2010 SDIBT TEAM
GPL2.0 2003-2010 HUSTOJ Project TEAM
Anything about the Problems, Please Contact Admin:admin