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

Cho một loại cấu trúc dữ liệu dạng tập hợp hỗ trợ hai thao tác sau:

• 1 x: Thêm phần tử x vào tập.
• 2: Bỏ một phần tử ra khỏi tập.

Cấu trúc dữ liệu trên có thể thuộc một trong ba dạng: stack, queue và priority_queue. Cho trước các thao tác và kết quả trả về của thao tác đó, nhiệm vụ của bạn là phân loại cấu trúc dữ liệu trên.

Input

Input gồm nhiều bộ test. Mỗi bộ test gồm:

• Dòng đầu tiên chứa số nguyên dương ~n~ là số lượng thao tác.
• ~n~ dòng sau, mỗi dòng chứa một trong hai thao tác:
  • ~1 \ x~: Thêm ~x~ vào trong tập.
  • ~2 \ x~: Bỏ một phần tử ra khỏi tập, ~x~ là kết quả mà thao tác này trả về.

Input được kết thúc bằng EOF (end-of-file). Input đảm bảo tổng ~n~ trong tất cả các test không quá ~2 \times 10^5~.

Output

• Với mỗi bộ test, in ra trên một kết quả theo cú pháp sau:
  • stack: Nếu cấu trúc dữ liệu ban đầu là stack.
  • queue: Nếu cấu trúc dữ liệu ban đầu là queue.
  • priority_queue: Nếu cấu trúc dữ liệu ban đầu là priority_queue.
  • not sure: Nếu cấu trúc dữ liệu ban đầu có thể là ít nhất hai trong ba cấu trúc dữ liệu trên.
  • impossible: Không cái nào trong ba cấu trúc dữ liệu trên là cấu trúc dữ liệu ban đầu.

Sample Input

3
1 6
2 1
1 1
4
1 4
1 1
2 1
2 4
4
1 1
1 7
2 1
2 7
4
1 8
1 9
1 7
2 9
3
1 1
2 1
1 6

Sample Output

impossible
stack
queue
priority queue
not sure

Cho một dãy số nguyên dương ~a~ gồm ~n~ phần tử. Một dãy được gọi là dãy tốt nếu với mọi số nguyên dương ~x~ mà có trong dãy ~a~, ~x~ xuất hiện trong dãy ~a~ đúng ~x~ lần. Hãy xóa đi ít phần tử nhất để ~a~ trở thành dãy tốt.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ ~(1 \le n \le 10^5)~.
• Dòng sau chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 10^9)~.

Output

• In ra một số nguyên duy nhất là số phần tử ít nhất cần phải xóa đi để dãy ~a~ trở thành dãy tốt.

Sample Input

8
2 7 1 8 2 8 1 8

Sample Output

5

Cho dãy ~a~ có ~m~ số nguyên ~a_1, a_2, \ldots, a_m~.

Dãy ~b~ có ~n~ số nguyên ~b_1, b_2, \ldots, b_n~. Hãy tìm số lượng phần tử trong dãy ~a~ xuất hiện trong dãy ~b~.

Input

Dòng đầu tiên chứa hai số nguyên ~m~ và ~n~ ~(0 < m, n \leq 10^5)~.

Dòng tiếp theo chứa ~m~ số nguyên ~a_i~ ~(-10^9 \leq a_i \leq 10^9)~.

Dòng tiếp theo chứa ~n~ số nguyên ~b_i~ ~(-10^9 \leq b_i \leq 10^9)~.

Output

Số lượng phần tử trong dãy ~a~ xuất hiện trong dãy ~b~.

Sample

Input

3 5
1 2 3
1 3 3 4 5

Output

2

Cho dãy ~a~ gồm ~n~ phần tử xếp thành một vòng tròn có giá trị bằng ~0~ và thực hiện ~m~ thao tác, mỗi thao tác gồm hai số ~(l, r)~ có ý nghĩa: tăng các phần tử có chỉ số từ ~l~ đến ~r~ thêm ~1~ đơn vị.

Sau khi thực hiện xong ~m~ thao tác, hãy tìm phần tử lớn nhất trong dãy và đưa ra số lần xuất hiện của phần tử đó trong dãy ~a~ mới.

Input

• Dòng đầu tiên chứa hai số nguyên ~n, m \ (1\le n\le 10^{18}, 1\le m\le 10^5)~.
• ~m~ dòng sau, mỗi dòng chứa hai số nguyên ~l_i, r_i \ (1\le l_i, r_i \le n, 1\le i\le m)~.

Output

Kết quả gồm hai số nguyên dương là đáp án của bài toán trên.

Ví dụ

Input

5 2
1 5
4 2

Output

2 4

Giải thích

Cho một bảng kích thước ~n~ dòng và ~m~ cột gồm các chữ cái, hãy xác định xem từ ~S~ có xuất hiện trong bảng hay không.

Một từ được gọi là xuất hiện trong bảng nếu:

• Nó có thể được ghép từ các ô kề nhau trong bảng.
• Một ô không thể sử dụng nhiều lần trong một từ.
• Hai ô kề nhau nếu chúng có chung cạnh (trái, phải, trên, hoặc dưới).

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~, là số dòng và số cột của bảng.
• ~n~ dòng tiếp theo, mỗi dòng chứa ~m~ ký tự, biểu diễn các ô trong bảng.
• Dòng cuối cùng chứa chuỗi ~S~ cần tìm.

Output

• In YES nếu từ ~S~ xuất hiện trong bảng.
• In NO nếu từ ~S~ không xuất hiện.

Điều kiện

• ~1 ≤ n, m ≤ 6~.
• Độ dài của ~S: 1 ≤ |S| ≤ 15~.
• Bảng chỉ chứa các chữ cái viết thường từ ~a~ đến ~z~.

Ví dụ

Input:

3 4
a b c e
s f c s
a d e e
see

Output:

YES

Giải thích:

• Từ "see" xuất hiện từ các ô (2,4) → (3,3) → (3,4).

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

Yêu cầu: Đếm số lượng ước số của ~N~ và tổng các ước số của ~N~.

Input

• Gồm một dòng duy nhất là số nguyên dương ~N~

Output

• Gồm hai số nguyên là sô lượng ước số và tổng các ước của ~N~

Constraints

• ~1 \le N \le 2 \times 10^9~.

Sample Test

Input

10 

Output

4 18

Explanation

• Số ~10~ có ước là ~1,~ ~2,~ ~5,~ ~10~ và tổng các ước là ~1 + 2 + 5 + 10 =18~

Cho mảng ~A~ gồm ~n~ số nguyên.

Bạn phải thay đổi ít nhất bao nhiêu số để mảng ~A~ chỉ gồm các số nguyên liên tiếp?

Input

• Dòng đầu tiên gồm số nguyên ~n~.
• Dòng thứ hai gồm ~n~ số nguyên ~A_i~.

Output

• In ra số lượng số nguyên ít nhất phải thay.

Điều kiện

• ~1 \le n \le 10^5~.
• ~1 \le A_i \le 10^9~.

Ví dụ

Input:

3
4 10 5

Output:

1

Chú ý: Thay ~10~ bằng ~6~.

Ràng buộc

• Subtask 1 ~(50\%)~: ~n \le 1000~.
• Subtask 2 ~(50\%)~: Không có ràng buộc gì thêm.

Một hàng rào bao gồm ~n~ bảng dọc. Chiều rộng của mỗi bảng là ~1~ và chiều cao của chúng có thể khác nhau.

Bạn muốn gắn một quảng cáo hình chữ nhật lên hàng rào. Diện tích tối đa của một quảng cáo như vậy là gì?

Input

• Dòng đầu vào đầu tiên chứa một số nguyên ~n~: chiều rộng của hàng rào.
• Sau này, có ~n~ số nguyên ~k_1, k_2, \dots, k_n~: chiều cao của mỗi bảng dọc.

Output

• In một số nguyên: diện tích tối đa của quảng cáo.

Constraints

• ~1 \le n \le 2 \cdot 10^5~
• ~1 \le k_i \le 10^9~

Example

Sample input

8
4 1 5 3 3 2 4 1

Sample output

10

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.

Sample Test

Input

8 2
8 4 2 1 1 3 5 9

Output

18

Cho số ~n~ và dãy số nguyên ~a~ gồm ~n~ phần tử, hãy tìm đoạn con liên tiếp dài nhất của dãy ~a~ có trung bình cộng lớn hơn hoặc bằng ~k~ cho trước.

Input

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

Output

• In ra một số nguyên là độ dài của dãy con liên tiếp dài nhất thỏa mãn.

Sample Test

Input

7 3
1 5 2 3 1 4 1

Output

5

Thao tác tăng hình nón đối xứng của một dãy số ~X_1,X_2,X_3,…,X_{N-2},X_{N-1},X_N~ được thực hiện như sau:

• Tăng ~X_1~ và ~X_N~ lên ~1~ đơn vị~;~
• Tăng ~X_2~ và ~X_{N-1}~ lên ~2~ đơn vị~;~
• Tăng ~X_3~ và ~X_{N-2}~ lên ~3~ đơn vị~;~
• ~…~

Cho một bảng hình vuông ~A~ có ~N~ dòng, ~N~ cột. Các dòng được đánh số từ ~1~ tới ~N~ theo thứ tự từ trên xuống dưới và các cột được đánh số từ ~1~ tới ~N~ theo thứ tự từ trái qua phải. Ô ở dòng thứ ~i~, cột thứ ~j~ được gọi là ô ~A(i,j)~. Ban đầu tất cả các ô đều có giá trị bằng ~0~. Thực hiện ~T~ thao tác tăng hình nón đối xứng trên bảng ~A~, mỗi thao tác có cấu trúc như sau: gồm bốn số nguyên dương ~k,rc,x,y~ ~(k=1~ hoặc ~k=2)~ có ý nghĩa:

• Khi ~k = 1,~ thực hiện tăng hình nón đối xứng trên dòng ~rc~ với dãy số gồm các số từ ~A(rc,x)~ đến ~A(rc,y);~
• Khi ~k = 2,~ thực hiện tăng hình nón đối xứng trên cột ~rc~ với dãy số gồm các số từ ~A(x,rc)~ đến ~A(y,rc)~.

Yêu cầu: Cho kích thước bảng, ~T~ thao tác tăng và ~Q~ câu hỏi. Mỗi câu hỏi có ý nghĩa: tìm giá trị của một ô của bảng sau khi thực hiện ~T~ thao tác.

Dữ liệu nhập vào từ file văn bản ITABLE.INP:

• Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~T~ là kích thước của bảng và số thao tác tăng. ~(N≤5000; \ T≤10^5)~
• ~T~ dòng sau, mỗi dòng gồm bốn số nguyên dương ~k,rc,x,y~ mô tả thao tác tăng lên dòng hoặc cột của bảng. ~(k=1~ hoặc ~k=2; \ rc,x,y≤N)~
• Dòng tiếp theo gồm số một số nguyên dương ~Q~ là số ô cần tìm giá trị. ~(Q≤10^5)~
• ~Q~ dòng sau, mỗi dòng chứa hai số nguyên dương ~u,v~ có ý nghĩa là cần tìm giá trị của ô ~A(u,v)~. ~(u,v≤N)~

Mỗi số cách nhau một dấu cách. Dữ liệu đảm bảo đúng đắn và luôn có kết quả.

Kết quả ghi ra file văn bản ITABLE.OUT:

Gồm ~Q~ dòng, mỗi dòng in ra giá trị của một ô tương ứng.

Ví dụ

Input

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

Output

0
2
4

Giải thích:

Giới hạn

• Có ~50\%~ số test tương ứng với số điểm có với ~T≤5000;~
• Có ~30\%~ số test khác tương ứng với số điểm có với ~Q≤500;~
• Có ~20\%~ số test còn lại tương ứng với số điểm không có giới hạn gì thêm~.~

Cho dãy ~A~ gồm ~n~ số nguyên. Hãy tìm cách chia dãy thành ~k~ nhóm mà các nhóm có tổng bằng nhau. Mỗi nhóm phải có ít nhất ~1~ phần tử.

Input

• Dòng đầu tiên gồm hai số nguyên ~n, k~.
• Dòng thứ hai gồm n số nguyên ~A{i}~.

Output

• In ra ~n~ số nguyên, số nguyên thứ ~i~ là nhóm của phần tử thứ ~i~. Nếu có nhiều đáp án, in ra đáp án bất kỳ.
• Nếu không tồn tại đáp án, in ra ~0~.

Điều kiện

• ~2 ≤ k < n ≤ 10~.
• ~1 ≤ Ai ≤ 100~.

Ví dụ

Input:

5 3
1 4 6 9 10

Output:

1 3 3 1 2

Giải thích:

• Nhóm đầu tiên gồm hai phần tử ~A{2} + A{3} = 4 + 6 = 10~.
• Nhóm thứ hai gồm một phần tử ~A{5} = 10~.
• Nhóm thứ ba gồm hai phần tử ~A{1} + A{4} = 1 + 9 = 10~.

Các đáp án như ~1 2 2 1 3~ hay ~3 1 1 3 2~ cũng được chấp nhận.

Cho một số nguyên, nhiệm vụ của bạn là tìm số lượng, tổng và tích của các ước số của nó. Ví dụ, chúng ta hãy xem xét số ~12~:

• số lượng ước số là ~6~ (chúng là ~1 , 2, 3, 4, 6, 12~)
• tổng của các ước số là ~1 + 2 + 3 + 4 + 6 + 12 = 28~
• tích của các ước số là ~1 \cdot 2 \cdot 3 \cdot 4 \cdot 6 \cdot 12 = 1728~

Vì số đầu vào có thể rất lớn, nó sẽ được cho dưới dạng phân tích thừa số nguyên tố.

Input

• Dòng đầu tiên có một số nguyên ~n~: số phần trong dạng phân tich thừa số nguyên tố.
• Sau đó, gồm ~n~ dòng mô tả dạng phân tích. Mỗi dòng có hai số ~x~ và ~k~, trong đó ~x~ là số nguyên tố và ~k~ là lũy thừa của nó.

Output

• In ba số nguyên chia lấy dư cho ~10 ^ 9 + 7~: số lượng, tổng và tích của các ước số.

Constraints

• ~1 \leq n \leq 10^5~
• ~2 \leq x \leq 10^6~
• mỗi ~x~ là một số nguyên tố riêng biệt
• ~1 \leq k \leq 10^9~

Example

Sample Input

2 
2 2
3 1

Sample Output

6 28 1728