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

Yakumo Ran rất thích làm toán, hôm nay cô nghiên cứu bài toán sau:

Cho một mảng ~a~ có ~n~ phần tử, cho ~q~ truy vấn dạng l r x, hãy đếm số lượng số có giá trị ~x~ trong đoạn ~a[l...r]~.

Hiện tại cô chưa có lời giải cho bài toán này nên nhờ các bạn giúp!

Input

• Dòng đầu tiên gồm hai số tự nhiên ~n, q \le 10^5~.
• Dòng tiếp theo là mảng ~a~ nguyên với ~1 \le a_i \le 10^9~.
• ~q~ dòng tiếp theo mỗi dòng gồm 3 số ~l_i, r_i, x_i~ là truy vấn thứ ~i~.

Output

• Với mỗi truy vấn in ra kết quả.

Sample Test

Input:

4 2
1 2 3 2
2 4 2
1 2 1

Output:

2
1

Bạn được nhận ~k \le 7~ chữ số ngẫu nhiên.

Yêu cầu: Dùng các chữ số bạn nhận được, hãy đếm xem có thể tạo ra được bao nhiêu số nguyên tố khác nhau.

Input

• Dòng đầu tiên là số ~T \le 10~ - số lượng test.
• ~T~ dòng tiếp theo, mỗi dòng gồm ~k~ chữ số tương ứng với một yêu cầu.

Output

• ~T~ dòng là kết quả của các test tương ứng theo thứ tự.

Sample Input 1

2
17
9999999

Sample Output 1

3
0

Giải thích

• Với ~2~ chữ số ~1,7~, tạo ra được 3 số nguyên tố là ~7, 17, 71~.
• Với ~7~ chữ số ~9~, không tạo ra được số nguyên tố nào.

Bạn được nhận ~n~ xâu kí tự, mỗi xâu gồm các chữ cái tiếng Anh in thường. Cần chọn ra một số xâu trong ~n~ xâu đó sao cho khi ghép tất cả chúng lại, ta được một xâu mới bao gồm đầy đủ các kí tự trong bảng chữ cái tiếng Anh. Hãy đếm số cách để thực hiện yêu cầu trên. Hai cách được coi là khác nhau khi có một xâu được chọn ở cách này không được chọn trong cách kia.

Input

- Dòng đầu tiên gồm số nguyên dương ~n~ ~(n \le 25)~ miêu tả số lượng xâu.

- ~n~ dòng tiếp theo, mỗi dòng bao gồm một xâu kí tự ~S~ ~(|S| \le 30)~ gồm các chữ cái tiếng Anh in thường.

Output

- In ra một số nguyên là kết quả bài toán.

Sample Input 1

8
the
quick
brown
fox
jumps
over
lazy
dog

Sample Output 1

1

Sample Input 2

3
a
b
abcdefghijklmnopqrstuvwxyz

Sample Output 2

4

Notes

Một xâu ~S~ được gọi là xâu đối xứng nếu ~S = S'~ với ~S'~ là xâu nhận được từ xâu ~S~ khi đọc từ phải qua trái. Ví dụ: Xâu ~'aba'~ là xâu đối xứng, còn xâu ~'abc'~ là xâu không đối xứng.

Cho một xâu ~S~ gồm ~1 \le n \le 1000~ kí tự.

Yêu cầu: Hãy tìm cách chia xâu ~S~ thành ít nhất các đoạn mà mỗi đoạn đều là các xâu đối xứng.

Input

• Dòng đầu gồm một số nguyên ~n~ là độ dài của xâu ~S~.
• Dòng thứ hai là nội dung xâu ~S~.

Output

• Dòng đầu ghi một số nguyên ~k~ (số đoạn ít nhất tìm được).
• ~K~ dòng sau, mỗi dòng ghi một số nguyên ~t_i~, với ~t_i~ là vị trí kết thúc của đoạn thứ ~i~.

Sample Input 1

 8
 abbacdcb

Sample Output 1

3
4
7
8

Cho dãy ~a~ gồm ~n~ phần tử nguyên và một số nguyên dương ~k~. Hãy in ra đoạn con liên tiếp có tổng lớn thứ ~k~. (Có ~n*(n+1)/2~ đoạn con liên tiếp trong dãy).

Input

• Dòng đầu gồm 2 số nguyên dương ~n~ ~(1 \le n \le 10^5)~ và ~k~ ~(1 \le k \le n*(n+1)/2)~.
• Dòng thứ 2 gồm ~n~ số nguyên miêu tả dãy ~a~. ~(-10^9 \le a_i \le 10^9)~.

Ouput

• In ra giá trị của đoạn con liên tiếp có tổng lớn thứ ~k~.

Sample Test

Input

4 3
1 -1 2 -2

Output

1

Giải thích: đoạn con ~[1,3], [3,3]~ là hai đoạn con có giá trị lớn nhất với tổng bằng ~2~. Tiếp đến là hai đoạn con ~[1,1], [2,3]~ có tổng bằng ~1~ có giá trị lớn thứ ~3~ và ~4~. Vậy đoạn con có giá trị lớn thứ ~k~ sẽ có giá trị bằng ~1~.