Giải bóng đá phong trào khối lớp \(9\) của trường Trung học cơ sở HB có ba đội tham gia là \(A, B, C\). Giải được tổ chức theo thể thức thi đấu vòng trong tính điểm: \(A\) gặp \(B\), \(A\) gặp \(C\), \(B\) gặp \(C\). Điểm mỗi trận được tính theo luật FIFA: Đội thắng được \(3\) điểm, đội thua được \(0\) điểm, nếu hòa thì mỗi đội được \(1\) điểm.

Kết quả trận \(A\) gặp \(B\) có tỉ số là \(p:q\) - Đội \(A\) ghi được \(p\) bàn thắng và bị thủng lưới \(q\) lần, kết quả trận \(A\) gặp \(C\) có tỉ số \(r:s\) - Đội \(A\) ghi được \(r\) bàn thắng và bị thủng lưới \(s\) lần, kết quả trận \(B\) gặp \(C\) có tỉ số \(u:v\) - Đội \(B\) ghi được \(u\) bàn và bị thủng lưới \(v\) lần.

Cho biết các số \(p, q, r, s, u, v\), hãy tính và đưa ra số điểm của mỗi đội.

Input

• Các số \(p, q, r, s, u, v\) (\(0 \leq p, q, r, s, u, v \leq 20\))

Output

• Ghi ba số lần lượt là số điểm của ba đội \(A, B, C\).

Example

9 7 7 5 4 8

6 0 3

Nội dung số học là một trong những chủ đề thú vị được khai thác rất nhiều trong các bài toán Tin học. Người ta có thể đưa ra những khái niệm mới đối với các số nguyên trong Tin học, ví dụ: số phong phú \(x\) là số mà tổng các ước (không kể chính nó) của nó lớn hơn \(x\), hoặc cắp số bạn bè \((a, b)\) mà tổng các ước (không tính \(a, b\)) của số này bằng số kia, \(\ldots\) Trong bài toán này, chúng ta định nghĩa cặp số đẹp \((a, b)\) là cặp số mà tổng các chữ số của \(a\) và \(b\) bằng nhau, ví dụ: \((14, 23)\) là cặp số đẹp vì \(1 + 4 = 2 + 3\), còn hai số \((14, 25)\) không phải cặp số đẹp vì \(1 + 4 \neq 2 + 5\).

Cho dãy số nguyên dương gồm \(n\) phần tử \(a_{1}, a_{2}, \ldots, a_{n}\). Hãy đếm số lương cặp số đẹp có trong dãy.

Input

• Dòng thứ nhất chứa số nguyên dương \(n\) (\(1 \leq n \leq 3*10^{5}\))
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_{1}, a_{2}, \ldots, a_{n}\) (\(a_{i} \leq 10^{9}\)). Các số cách nhau bởi dấu cách.

Output

• Một số nguyên duy nhất là số lượng cặp số đẹp tìm được.

Example

5
3 8 21 17 12

4

Có 4 cặp số đẹp là (3, 21), (8, 17), (21, 12), (3, 12). 

Giới hạn

• Subtask \(1\): Có \(70\%\) số test đầu tiên \(n \leq 1000\).
• Subtask \(2\): Có \(30\%\) số test còn lại \(n \leq 3*10^{5}\).

Tầng áp mái thường được sử dụng như nhà kho lưu trữ các giấy tờ, đồ đạc cũ và ít ai lên đó. Hôm nay, Bình có việc cần lên đó tìm cuốn album lưu ảnh của những thế hệ trước trong gia đình.

Ô khóa mở cánh cửa có hai núm xoay hình tròn, núm thứ nhất đang chỉ tới số \(a\), núm thứ hai đang chỉ tới số \(b\). Các núm chỉ có thể xoay theo chiều kim đồng hồ. Khi xoay một vòng, sô được chỉ sẽ tăng thêm \(1\). Cánh cửa sẽ mở khi các số \(a\) và \(b\) nhận được có ước chung khác \(1\).

Đáng tiếc, do để lâu không dùng núm thứ nhất bị kẹt, không xoay được và vì vậy luôn chỉ tới số \(a\). Như vậy chỉ có thể xoay núm thứ hai.

Hãy xác định số vòng xoay tối thiểu cần thực hiện của núm thứ hai để mở cửa.

Input

• Dòng thứ nhất chứa số nguyên \(n\) là số cặp \(a, b\) \((1 \leq n \leq 100)\)
• Dòng thứ \(i\) trong \(n\) dòng sau chứa \(2\) số nguyên \(a\) và \(b\), ghi cách nhau một dấu cách \((2 \leq a, b \leq 10^{9})\).

Output

• Với mỗi test đã cho đưa ra trên một dòng một số nguyên là lời giải tìm được.

Example

3
15 7
23 11
35 42

2
12 
0

Ràng buộc

• Subtask \(1\): \(50\%\) số test tương ứng với \(n = 1, 1 \leq a, b \leq 10^{5}\).
• Subtask \(2\): \(30\%\) số test tiếp theo tương ứng với \(1 \leq a, b \leq 10^{5}\).
• Subtask \(3\): \(20\%\) số test còn lại không có ràng buộc gì.

Hội thi Olympic Khoa học viễn tưởng là hội thi thường niên diễn ra giữa các trường trung học cơ sở trên cả nước, ngoài nội dung thi kiến thức học sinh giỏi, Ban tổ chức còn có nội dung thi vận động dành cho các bạn học sinh. Năm nay, hội thi được tổ chức tại trường Ngôi Sao - thành phố XYZ. Ban tổ chức sẽ có một trò chơi vận động mới đó là cuộc thi xếp tháp dành cho các đội chơi.

Mỗi đội chơi sẽ được Ban tổ chức cung cấp \(n\) khối hộp, và các đội phải xếp thành các tòa tháp thỏa mãn các yêu cầu sau:

• Mỗi đội nhận khối hợp đầu tiên và tạo tháp đầu tiên.
• Khi nhận được một khối hộp các đội phải xếp luôn và tháp đã có hoặc tạo ra một tháp mới, sau đó mới được nhận khối hộp tiếp theo từ Ban tổ chức.
• Các tòa tháp phải thỏa mãn điều kiện khối hộp ở trên có thể thích không lớn hơn khối hộp ở ngay dưới nó.
• Không được chuyển khối hộp từ tòa tháp này sang tòa tháp khác.
• Mỗi đội cần phải xếp được càng ít tòa tháp càng tốt.

Bạn là một thành viên của trường Trung học cơ sở HB tham gia cuộc thi xếp tháp, nhiệm vụ của bạn và đồng đội của mình là xếp được các tòa tháp thỏa mãn điều kiện của Ban tổ chức đưa ra.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) là số lượng các khối hộp mà Ban tổ chức cung cấp cho trường Trung học cơ sở HB.
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_{1}, a_{2}, \ldots, a_{n}\) \((a_{i} \leq 10^{9})\) là thể tích của các khối hộp.

Output

• Một dòng duy nhất là số lượng tòa tháp ít nhất được tạo thành.

Example

5
3 8 5 2 2

2

Ràng buộc

• Subtask \(1\): \(70\%\) số test tương ứng với \(1 \leq n \leq 1000\).
• Subtask \(2\): \(30\%\) số test tiếp theo tương ứng với \(1 \leq n \leq 3*10^{5}\).