Cho dãy số nguyên \(a\) gồm \(n\) phần tử. Hãy tính tổng của \(|a_i-a_j|\) với mọi cặp \((i,j)\) thỏa mãn \(1 \le i < j \le n\).

Input

• Dòng đầu gồm \(1\) số nguyên \(n\) \((1 \le n \le 10^5)\).
• Dòng sau gồm \(n\) số nguyên miêu tả dãy \(a\) \((|a_i| \le 10^6)\)

Output

• In ra kết quả tìm được.

Sample Test

Input

3
5 1 2

Output

8

Công ty đồ chơi X nhập khẩu n con búp bê gỗ. Các con búp bê được đánh số từ 1 tới n trong đó con búp bê thứ i là một hộp rỗng có kích thước là một số nguyên ai. Người ta có thể lồng con búp bê thứ i vào trong con búp bê thứ j nếu con búp bê thứ j đang rỗng và \(a_i+k ≤ a_j\), với k là một số nguyên dương cho trước. Bằng cách lồng các con búp bê vào nhau theo cách như vậy, công ty X chỉ cần tìm chỗ đặt những con búp bê ngoài cùng (những con búp bê không nằm trong bất kỳ con búp bê nào khác) vào kho.

Yêu cầu: Hãy giúp công ty X lồng các con búp bê vào nhau sao cho tổng kích thước các con búp bê ngoài cùng là nhỏ nhất.

Input

Gồm 2 dòng

• Dòng 1 chứa hai số nguyên dương \(n ≤ 10^5\); \(k ≤ 10^9\) cách nhau một khoảng trắng.

• Dòng 2 chứa n số nguyên dương \(a_1, a_2, ..., a_n\) ( \(a_i ≤ 10^9\)), mỗi số cách nhau một khoảng trắng.

Output

• Là một số nguyên duy nhất là tổng kích thước các con búp bê ngoài cùng theo phương án tìm được.

Example

8 2
8 4 2 1 1 3 5 9

18

Cho một dãy \(a\) gồm \(n\) phần tử nguyên không âm.

Có \(q\) truy vấn, mỗi truy vấn có dạng \(l,r,d\), có nghĩa là tăng phần tử thứ \(l\) lên \(d\) đơn vị, phần tử thứ \(l+1\) lên \(2*d\) đơn vị, ..., phần tử thứ \(r\) lên \((r-l+1)*d\) đơn vị. Nói cách khác, phần tử thứ \(i \in [l,r]\) sẽ được tăng thêm \((i-l+1)*d\) đơn vị.

Hãy in ra dãy \(a\) sau khi thực hiện đủ \(q\) truy vấn.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\)
• Dòng thứ hai gồm \(n\) số nguyên không âm miêu tả dãy \(a\).
• \(q\) dòng sau, mỗi dòng gồm \(3\) số nguyên \((l,r,d)\) miêu tả truy vấn.

Output

• Gồm một dòng in ra \(n\) số, số thứ \(i\) là giá trị của phần tử \(a_i\) sau khi thực hiện \(q\) truy vấn.

Điều kiện

• \(1 \le n,q \le 10^6\).
• \(0 \le a_i,d_i \le 10^5\).

Subtask

• \(50\%\) số điểm: \(n \le 1000\).
• \(50\%\) số điểm: \(n \le 10^5\).

Example

1
10
3
1 1 40
1 1 0
1 1 -15

35 

5
1 2 3 4 -5
3
5 5 10
1 5 4
2 3 -1

5 9 13 20 25 

Trên mặt phẳng toạ độ \(Oxy\) có \(N\) điểm màu đỏ và \(N\) điểm màu xanh. Điểm màu đỏ thứ \(i\) có toạ độ \((a_i, b_i)\) và điểm màu xanh có toạ độ \((c_i, d_i)\). Tất cả các điểm đều có hoành độ và tung độ phân biệt.

Một điểm đỏ và một điểm xanh có thể tạo thành một cặp thân thiện khi và chỉ khi hoành độ của điểm đỏ nhỏ hơn hoành độ của điểm xanh, và tung độ của điểm đỏ nhỏ hơn tung độ của điểm xanh. Nói cách khác, điểm đỏ thứ \(i\) và điểm xanh thứ \(j\) có thể tạo thành một cặp thân thiện khi và chỉ khi \(a_i < c_j\) và \(b_i < d_j\).

Hãy cho biết có thể tạo tối đa bao nhiêu cặp thân thiện, sao cho mỗi điểm chỉ thuộc tối đa một cặp thân thiện.

Input

• Dòng đầu tiên gồm số nguyên \(N\) (\(1 \leq N \leq 10^5\)) - số điểm đỏ cũng như số điểm xanh.
• \(N\) dòng tiếp theo, dòng thứ \(i\) gồm hai số nguyên \(a_i\) và \(b_i\) (\(10^9 \leq a_i, b_i \leq 10^9\)) - toạ độ của điểm đỏ thứ \(i\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) gồm hai số nguyên \(c_i\) và \(d_i\) (\(10^9 \leq c_i, d_i \leq 10^9\)) - toạ độ của điểm xanh thứ \(i\).

Dữ liệu vào đảm bảo các số nguyên \(a_1, a_2, \ldots, a_N, c_1, c_2, \ldots, c_N\) khác nhau từng dôi một, và các số nguyên \(b_1, b_2, \ldots, b_N, d_1, d_2, \ldots, d_N\) khác nhau từng dôi một.

Output

• In ra một số nguyên duy nhất là số cặp thân thiện tối đa có thể tạo được

Subtasks

• \(25\%\) số test có \(N \leq 8\).
• \(25\%\) số test có \(N \leq 16\).
• \(25\%\) số test có \(N \leq 1000\).
• \(25\%\) số test có \(N \leq 10^5\).

Sample Test 1

Input:

3
-2 -2
-3 1
1 3
2 0
-1 4
3 -1

Output:

2

Sample Test 2

Input:

3
-3 3
-2 2
-1 1
1 -1
2 -2
3 -3

Output:

0

Bạn được cho mảng gồm \(N\) số nguyên và một số nguyên \(K\). Nhiệm vụ của bạn là đi tìm giá trị lớn nhất của tất cả mảng con liền kề có độ dài \(K\), của mảng ban đầu.

Input

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test cases (\(1 \leq T \leq 500\))
• Với mỗi test case, nhập vào số nguyên \(N\) và \(K\), theo sau đó là \(N\) phần tử \(A_i\) của mảng (\(1 \leq K \leq N \leq 10^4\), \(1 \leq A_i \leq 10^4\)).

Output

• Với mỗi mảng con liền kề độ dài \(K\), in ra giá trị lớn nhất

Sample Test

Input:

2
5 2
3 4 6 3 4
7 4
3 4 5 8 1 4 10

Output:

4 6 6 4
8 8 8 10

Mrtee mở căng-tin bán đồ ăn có tổng cộng \(N\) loại bánh, loại bánh thứ \(i\) sẽ có giá gốc là \(A_i\) và giá tiền bán ra là \(B_i\). Để khỏi bị lỗ, Mrtee sẽ bán bánh theo một cặp (\(i\), \(j\)) như sau:

• \(1 \leq i < j \leq N\)
• \(A_i + A_j = B_i + B_j\)

Nếu theo cách trên thì có bao nhiêu cặp loại bánh có thể bán.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) (\(1 \leq N \leq 2 \times 10^5\))
• \(N\) dòng tiếp theo, dòng thứ \(i\) gồm \(2\) số nguyên dương \(A_i\), \(B_i\) (\(1 \leq A_i, B_i \leq 10^9\))

Output

• In ra kết quả thỏa mãn.

Sample Test

Input:

3
1 2
4 3
2 1

Output:

2