Vadim nhỏ bé có một bài tập ở trường: cậu ấy phải mô tả các nhân vật trong một tác phẩm văn học nổi tiếng. Vadim đã hoàn thành bài tập của mình một cách xuất sắc và vẽ một bản báo cáo dưới dạng bảng tính trong trình soạn thảo văn bản yêu thích của mình.

Bảng tính có cấu trúc như sau. Đó là một bảng kích thước $3 \times 3$. Tại giao điểm của hàng thứ $i$ và cột thứ $j$, một đoạn văn bản có độ dài $a_{ij}$ được đặt vào. Tổng chiều rộng của bảng là $w$ ký tự. Trình soạn thảo văn bản cho phép thay đổi chiều rộng của mỗi cột theo cách tùy ý. Gọi chiều rộng của các cột lần lượt là $x, y, z$, và $x + y + z = w$. Khi đó, chiều cao của hàng thứ $i$ là $h_i = \max(\lceil a_{i1}/x \rceil, \lceil a_{i2}/y \rceil, \lceil a_{i3}/z \rceil)$, và tổng chiều cao của bảng là $h = h_1 + h_2 + h_3$.

Vadim nhận thấy rằng việc thay đổi chiều rộng của các cột làm thay đổi chiều cao của toàn bộ bảng theo cách khó dự đoán. Vadim là một người cầu toàn, và cậu ấy muốn thay đổi chiều rộng của các cột sao cho tổng chiều cao của bảng là nhỏ nhất.

Hãy giúp Vadim tìm ra giải pháp tối ưu.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $w$ ($3 \le w \le 10^9$).

Ba dòng tiếp theo, mỗi dòng chứa ba số nguyên. Số thứ $j$ trong dòng thứ $i$ của các dòng này là số nguyên $a_{ij}$ ($1 \le a_{ij} \le 10^{12}$).

Dữ liệu ra

Dòng đầu tiên in ra số nguyên $h$ — chiều cao tối thiểu có thể có của toàn bộ bảng.

Dòng thứ hai in ra ba số nguyên $x, y$ và $z$ — chiều rộng của các cột tạo ra giải pháp tối ưu.

Nếu có nhiều giải pháp, hãy in ra bất kỳ giải pháp nào trong số đó.

Ví dụ

Dữ liệu vào 1

17
10 11 11
13 7 14
10 11 11

Dữ liệu ra 1

7
5 6 6

Ghi chú

Bảng sau đây khớp với dữ liệu từ ví dụ đầu tiên: