Problem
Kazuma du hành cùng ba người bạn đồng hành: Aqua, Megumin và Darkness. Nhưng việc đi lại không được trả tiền, vì vậy đội của chúng tôi phải hoàn thành các nhiệm vụ do Hội thám hiểm giao cho.
Kazuma đã chọn n nhiệm vụ để hoàn thành. Tuy nhiên, bất cứ khi nào một đội đầy đủ lực lượng đảm nhận một việc gì đó, những điều không lường trước được và vô lý sẽ xảy ra. Đó là lý do tại sao Kazuma quyết định rằng đối với mỗi nhiệm vụ, anh ấy sẽ có
chính xác hai bạn đồng hành.
Tỷ lệ của mỗi người bạn đồng hành với Kazuma được đặc trưng bởi một số nguyên. Ban đầu, thái độ của mỗi người trong số họ là trung lập và bằng 0. Trong quá trình hoàn thành nhiệm vụ, thái độ của những cô gái anh nhận nhiệm vụ đối với anh thay đổi theo hướng tích cực hoặc tiêu cực (hoặc có thể không thay đổi gì cả) .
Đối với mỗi nhiệm vụ, Kazuma biết thái độ của mỗi cô gái đối với anh sẽ thay đổi như thế nào sau khi hoàn thành nhiệm vụ. Anh ấy muốn đưa bạn đồng hành làm nhiệm vụ để sau khi hoàn thành tất cả chúng, thái độ của tất cả các cô gái đối với anh ấy đều bình đẳng. Nếu điều này có thể đạt được theo nhiều cách khác nhau, thì tất nhiên, điều cần thiết là mối quan hệ phải càng tốt càng tốt.
Hãy giúp Kazuma tìm ra cách đối xử bình đẳng nhất mà anh ấy có thể dành cho tất cả các cô gái.
Đầu vào:
Dòng đầu tiên chứa số nguyên dương n (1 ≤ n ≤ 25) — số lượng nhiệm vụ cần hoàn thành.
N dòng tiếp theo chứa các mô tả về — Dòng thứ i chứa ba số a
i, m
i, d
i — mức độ mà thái độ của Aqua, Megumin hoặc Darkness đối với Kazuma sẽ thay đổi tương ứng, nếu anh hùng đưa họ đi cùng để hoàn thành nhiệm vụ thứ i.
Tất cả các số nhập vào đều là số nguyên và không vượt quá 10
7 về giá trị tuyệt đối.
Đầu ra:
Nếu không có giải pháp nào, hãy in "Không thể" ở dòng đầu tiên.
Nếu không, hãy in mối quan hệ mà tất cả các cô gái sẽ có đối với Kazuma, đồng thời, in tối đa có thể.
Ví dụ:
| Đầu vào |
Đầu ra |
3
1 0 0
0 1 0
0 0 1
| 1 |
7
0 8 9
5 9 -2
6-8-7
9 4 5
-4 -9 9
-4 5 2
-6 8 -7
| 5 |
2
1 0 0
1 1 0
| Không thể |