Cho dãy số sau: 2 6 12 20 30 42..

Yêu cầu: Hãy tìm số hạng thứ ~N~ của dãy trên.

Dữ liệu vào:

• Số nguyên dương ~N~ (~1 \le N \le 10^9~).

Dữ liệu ra:

• Số nguyên duy nhất là kết quả bài toán.

Ví dụ:

Input

5

Output

30

Cho dãy số sau: 1 5 12 22 35..

Yêu cầu: Hãy tìm số hạng thứ ~N~ của dãy trên.

Dữ liệu vào:

• Số nguyên dương ~N~ (~1 \le N \le 10^9~).

Dữ liệu ra:

• Số nguyên duy nhất là kết quả bài toán.

Ví dụ:

Input

4

Output

22

Cho dãy số sau: 1 3 5 7 9 11 13... Các số được đánh thứ tự bắt đầu từ 1.

Yêu cầu: Hãy tính tổng các số hạng từ số thứ x đến số thứ y trong dãy trên.

Dữ liệu vào:

• Nhập vào 2 số nguyên dương ~x~, ~y~ (~1 \le x \le y \le 10^9~).

Dữ liệu ra:

• Số nguyên duy nhất là kết quả bài toán.

Ví dụ:

Input

2 5

Output

24

Cho dãy số sau: 3 6 9 12 15 18 21... Các số được đánh thứ tự bắt đầu từ 1.

Yêu cầu: Hãy tính tổng các số hạng từ số thứ x đến số thứ y trong dãy trên.

Dữ liệu vào:

• Nhập vào 2 số nguyên dương ~x~, ~y~ (~1 \le x \le y \le 10^9~).

Dữ liệu ra:

• Số nguyên duy nhất là kết quả bài toán.

Ví dụ:

Input

2 5

Output

42

Cho dãy số sau: 2 7 12 17 22 27... Các số được đánh thứ tự bắt đầu từ 1.

Yêu cầu: Hãy tính tổng các số hạng từ số thứ x đến số thứ y trong dãy trên.

Dữ liệu vào:

• Dòng 1. Số nguyên dương N - Là số bộ test(~1 \le N \le 10^6~)
• N dòng tiếp theo mỗi dòng ghi 2 số nguyên dương ~x~, ~y~ (~1 \le x \le y \le 10^9~).

Dữ liệu ra:

• Gồm N dòng, mỗi dòng ghi 1 số nguyên k là tổng các phần tử từ x đến y ứng với N bộ test đã cho.

Ví dụ:

Input

2
2 5
1 3

Output

58
21

Cho dãy số sau: 1 3 5 7 9 11 13... Các số được đánh thứ tự bắt đầu từ 1.

Yêu cầu: Hãy tính tổng các số hạng từ số thứ x đến số thứ y trong dãy trên.

Dữ liệu vào:

• Dòng 1. Số nguyên dương N - Là số bộ test(~1 \le N \le 10^6~)
• N dòng tiếp theo mỗi dòng ghi 2 số nguyên dương ~x~, ~y~ (~1 \le x \le y \le 10^9~).

Dữ liệu ra:

• Gồm N dòng, mỗi dòng ghi 1 số nguyên k là tổng các phần tử từ x đến y ứng với N bộ test đã cho.

Ví dụ:

Input

2
2 5
1 3

Output

24
9

Cho một số nguyên dương ~N~.

Yêu cầu: Tìm ~T~ là số cách phân tích số ~N~ thành tổng của các số nguyên dương liên tiếp.

Ví dụ: ~N~= 15. Có 3 cách phân tích số 15 thành tổng các số nguyên dương liên tiếp như sau: 15 = 1+2+3+4+5 = 4+5+6 = 7+8

Input:

• Nhập vào một số nguyên dương ~N~(~2 < N ≤ 10^{12})~

Output:

• Ghi ra số T tìm được

Example:

Input:

15

Output:

3

Cho một dãy gồm ~n~ số nguyên dương.

Yêu cầu: Xác định số cách chọn hai phần tử trong dãy số sao cho tổng hai phần tử này có giá trị lẻ.

Input

• Dòng thứ nhất ghi số nguyên dương ~n~ (~1≤n≤10^6~).

• Dòng thứ hai ghi ~n~ số nguyên dương ~a_i~ (~1≤a_i≤10^6~).

Output

• Một số là kết quả tìm được.

Examples

Input1

4
1 3 5 6

Output1

3

Input2

5
2 4 7 8 6

Output2

4

Note

• Giải thích ví dụ 1: Các cặp số được chọn là (1;6),(3;6),(5;6).

• Giải thích ví dụ 2: Các cặp số được chọn là (2;7),(4;7),(7;8),(7;6).

Cho số nguyên dương ~N~ (~1 \le N \le 5.10^9~).

Yêu cầu: Tính tổng các số chia hết cho 3 nhưng không chia hết cho 5 trong đoạn từ 1 đến ~N~.

Dữ liệu vào:

• Gồm 1 dòng duy nhất ghi số nguyên dương ~N~.

Dữ liệu ra:

• Ghi số nguyên dương ~T~ là kết quả bài toán.

Ví dụ:

Input

15

Output

30

Cho số nguyên dương ~N~ (~1 \le N \le 5.10^9~).

Yêu cầu: Tính tổng các số chia hết cho 3 nhưng không chia hết cho 7 trong đoạn từ 1 đến n.

Dữ liệu vào:

• Gồm 1 dòng duy nhất ghi số nguyên dương ~N~.

Dữ liệu ra:

• Ghi số nguyên dương ~T~ là kết quả bài toán.

Ví dụ:

Input

22

Output

63

Cho dãy số ~A~ gồm ~n~ phần tử nguyên dương ~A_1,A_2,…,A_n~. Mỗi phần tử có giá trị không vượt quá ~10^9~ và ~1<n≤5000~. Một bộ ba số được gọi là bộ số tam giác, nếu ba số này tạo thành ba cạnh của một tam giác nào đó.</p>

Yêu cầu: Hãy đếm xem trong dãy ~A~ có bao nhiêu bộ số tam giác ~(A_i,A_j,A_k~) với ~i~,~j~,~k~ đôi một khác nhau.

Dữ liệu vào

• Dòng đầu là số ~n~.
• Dòng tiếp theo là các phần tử của dãy ~A~, mỗi phần tử cách nhau một dấu cách.

Dữ liệu ra:

• Ghi ra số lượng bộ số tam giác.

Scoring

Subtask 1: (30% số điểm): ~n≤100~.

Subtask 2: (30% số điểm): ~100<n≤1000~.</p>

Subtask 3: (40% số điểm): ~1000<n≤5000~.</p>

Example

Input

5
4 3 1 5 7 

Output

3

Cho ~N~ bình chứa nước lần lượt có thể tích là các số ~a_1.. a_N~. Khi xếp các bình theo một dãy thì sẽ tạo thành 1 khối. Nếu xếp lần lượt các bình chứa nước theo trình tự đó thì thể tích cả khối là ~a_1 + a_2 + ... + a_N + max(0, a_2 - a_1) + max(0, a_3 - a_2) + ... + max(0,a_N - a_{N - 1}~. Nhiệm vụ của bạn là tìm cách xếp sao cho tổng thể tích chứa của cả khối là lớn nhất có thể.

Dữ liệu:

• Dòng đầu ghi số nguyên dương ~N~ (~0 < n ≤ 10^5~).
• ~N~ dòng sau mỗi dòng ghi một số ~a_i~ ( ~1 ≤ i ≤ N và 1 ≤ a_i ≤ 10000~).

Kết quả:

• Ghi trên một dòng kết quả là thể tích lớn nhất tìm được.

Ví dụ

Input

4
5 4 1 7

Output

24

Một học sinh chuẩn bị cho năm học mới của mình nên đã đi đến một cửa hàng mua viết và tập. Trong hai lần mua sắm, học sinh đều mua cùng số lượng viết và cùng số lượng tập. Tuy nhiên, trong hai lần mua sắm này, học sinh mua viết và tập khác loại nhau nên đơn giá có thể không giống nhau.

Trong lần mua thứ nhất, học sinh mua với đơn giá viết là ~v1~ đồng và đơn giá tập là ~t1~ đồng. Tổng số tiền phải trả trong lần này là ~s1~ đồng.

Trong lần mua thứ hai, học sinh mua với đơn giá viết là ~v2~ đồng và đơn giá tập là ~t2~ đồng. Tổng số tiền phải trả trong lần này là ~s2~ đồng.

Yêu cầu: Xác định tổng số lượng viết và tổng số lượng tập mà học sinh đã mua trong cả hai lần.

Input

• Dòng đầu chứa ba số nguyên dương ~v1~,~t1~,~s1~, lần lượt cho biết đơn giá viết, đơn giá tập và tổng số tiền phải trả trong lần mua thứ nhất.

• Dòng thứ hai chứa ba số nguyên dương ~v2~,~t2~,~s2~, lần lượt cho biết đơn giá viết, đơn giá tập và tổng số tiền phải trả trong lần mua thứ hai.

Lưu ý: Các số có giá trị không vượt quá ~10^9~, dữ liệu cho đảm bảo luôn tìm được đúng một đáp án và đáp án luôn có giá trị là số nguyên không âm.

Output

• Hai số nguyên tương ứng với tổng số lượng viết và tổng số lượng tập mà học sinh đã mua.

Example

Input

7000 10000 78000
6500 11000 81000

Output

8 10