Hàng ngày hành trình của An là từ nhà đi đến trường. Khi học xong ở trường An luôn đi đến thư viện tỉnh đọc sách và tự học. Cuối ngày, khi kết thúc việc đọc sách ở thư viện An đi về nhà mình. Có ba con đường. Con đường thứ nhất từ nhà An đến trường có độ dài ~a~ (đơn vị); con đường thứ hai từ nhà An đến thư viện có độ dài ~b~ (đơn vị); con đường thứ ba từ trường đến thư viện có độ dài ~c~ (đơn vị). An chỉ di chuyển trên các con đường này để hoàn thành hành trình của mình.

Yêu cầu: Hãy tính độ dài hành trình ngắn nhất mà An thực hiện trong một ngày.

Input

Gồm 3 dòng, mỗi dòng chứa một số nguyên lần lượt là giá trị của ~a, b~ và ~c~ (~1 \le a, b, c \le 10^6~).

Output

Ghi ra một số nguyên duy nhất là độ dài ngắn nhất của hành trình An thực hiện.

Sample Input 1

1
1
3

Sample Output 1

4

Có một máy tự động rút tiền (ATM) với số tiền hiện có trong máy là ~T~. Có ~n~ người lần lượt đến rút tiền theo thứ tự 1, 2, ..., ~n~. Người thứ ~i~ yêu cầu rút số tiền là ~a_i~. ATM hoạt động theo nguyên tắc: "Nếu số tiền mà người yêu cầu rút không vượt quá số tiền hiện có trong ATM thì người này sẽ nhận được số tiền theo đúng yêu cầu, ngược lại ATM sẽ từ chối và người định rút không nhận được số tiền nào cả. Anh ta sẽ buồn bã bỏ đi!".

Yêu cầu: Hỏi rằng có bao nhiêu người buồn bã bỏ đi?

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n, T~ lần lượt là số người đến rút tiền và số tiền ban đầu có trong máy ATM (~n \le 10^5; T \le 10^9~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~a_i \le 10^9~ với mọi ~i = 1, 2, ..., n~). Hai số liên tiếp trên cùng một dòng cách nhau bằng khoảng trống (space).

Output

Ghi ra một số nguyên duy nhất là số người buồn bã bỏ đi.

Sample Input 1

4 5
2 5 1 4

Sample Output 1

2

Cho dãy ~n~ số nguyên ~a_1, a_2, ..., a_n~. Hãy tìm dãy con gồm các số liên tiếp của dãy trên ~a_i, a_{i+1}, ..., a_j~ (~1 \le i \le j \le n~) sao cho tổng ~a_i + a_{i+1} + ... + a_j~ đạt giá trị lớn nhất.

Yêu cầu: Hãy tính giá trị tổng lớn nhất này.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ (~n \le 10^6~).
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~|a_i| \le 10^3; \forall i = 1, 2, ..., n~). Hai số liên tiếp trên cùng một dòng cách nhau bằng khoảng trống (space).

Output

Ghi ra màn hình duy nhất một số nguyên là kết quả tìm được.

Sample Input 1

5
-5 2 -1 0 4

Sample Output 1

5

Giải thích: Dãy con có tổng lớn nhất là 2, -1, 0, 4 (tổng là 5).

Subtasks

• Có 40% số tests ứng với 40% số điểm của bài có ~n \le 500~.
• 40% số tests tiếp theo ứng với 40% số điểm của bài có ~n \le 5000~.
• 20% số tests còn lại không có ràng buộc bổ sung.

Trong một tòa nhà mới xây có ~T~ căn phòng. Nền căn phòng thứ ~i~ có dạng hình chữ nhật với kích thước ~m_i \times n_i~ (~m_i~ đơn vị chiều dài và ~n_i~ đơn vị chiều rộng). Người ta muốn lát sàn phòng này bằng các viên gạch hình vuông giống nhau cùng độ dài cạnh là ~k~, với ~k~ là một số nguyên dương. Hỏi rằng với mỗi căn phòng có bao nhiêu cách chọn loại gạch khác nhau để toàn bộ diện tích của căn phòng được lát kín bằng các viên gạch mà không phải cắt bỏ bất kỳ viên gạch nào. Giả thiết khoảng trống giữa các viên gạch bằng 0.

Yêu cầu: Cho ~T~ căn phòng với kích thước tương ứng, hãy tính số cách chọn gạch cho mỗi phòng.

Input

• Dòng đầu chứa số nguyên dương ~T~ (~T \le 2 \times 10^5~) là số căn phòng.
• Tiếp theo là ~T~ dòng, dòng thứ ~i~ chứa hai số nguyên dương ~m_i, n_i~ (~m_i, n_i \le 5 \times 10^5~) mô tả kích thước nền của phòng thứ ~i~.

Output

Ghi ra màn hình gồm ~T~ dòng, dòng thứ ~i~ ghi duy nhất một số nguyên là số cách khác nhau chọn kích thước viên gạch vuông để lát phòng thứ ~i~.

Sample Input 1

2
12 18
4 3

Sample Output 1

4
1

Giải thích:

• Căn phòng thứ nhất có 4 cách chọn gạch lát nền với kích thước viên gạch là ~k = 1, 2, 3, 6~.
• Căn phòng thứ hai chỉ có duy nhất một cách lát nền với kích thước viên gạch ~k = 1~.

Subtasks

• Có 50% số tests ứng với 50% số điểm của bài có ~T = 1; m_i, n_i \le 100~.
• 25% số tests tiếp theo ứng với 25% số điểm của bài có ~m_i, n_i \le 10^4~.
• 25% số tests còn lại không có ràng buộc bổ sung.

Một số nguyên dương được gọi là "số đẹp" nếu nó chia hết cho ~M~. Bài tập nghỉ hè của thầy giáo cho An là "Hãy đếm xem có bao nhiêu cặp số ~(x, y)~ với ~1 \le x < y \le n~ sao cho tổng ~x + y~ là số đẹp?" Là một người chuẩn bị vào học lớp chuyên Tin học, bạn hãy viết một chương trình giúp An giải quyết bài toán trên.

Yêu cầu: Đếm số lượng cặp số ~(x, y)~ thỏa mãn điều kiện đề bài.

Input

Dữ liệu nhập từ bàn phím một dòng duy nhất chứa hai số nguyên dương ~n, M~ (~n, M \le 10^9~).

Output

Ghi ra màn hình duy nhất một số nguyên dương là số cặp số tìm được.

Sample Input 1

7 5

Sample Output 1

4

Giải thích: Các cặp số tìm được lần lượt là ~(1, 4), (2, 3), (3, 7), (4, 6)~.

Subtasks

• Có 30% số tests ứng với 30% số điểm của bài có ~n, M \le 5000~.
• 30% số tests tiếp theo ứng với 30% số điểm của bài có ~n, M \le 10^6~.
• 20% số tests tiếp theo ứng với 20% số điểm của bài có ~n \le 10^9; M \le 10^6~.
• 20% số tests còn lại không có ràng buộc bổ sung.