Cho một dãy gồm ~n~ số nguyên dương ~A_1,A_2,\ldots,A_n~.

Yêu cầu: Hãy in ra tất cả các số trong mảng ~A~ cùng với số lần xuất hiện của chúng.

Input

• Dòng đầu chứa số ~n~ (~n\leq 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~A_1,A_2,\ldots,A_n~ (~A_i\leq 10^6~).

Output

• Gồm ~n~ dòng, mỗi dòng ghi số hạng thứ ~A_i~ và số lần xuất hiện của chúng.

Example

Input

9
2 3 1 2 3 4 5 4 3

Output

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

Cho một dãy gồm ~n~ số nguyên dương ~A_1,A_2,\ldots,A_n~..

Yêu cầu: Hãy in ra các phần tử của mảng theo thứ tự tăng dần cùng với số lần xuất hiện của chúng, các số trùng nhau thì chỉ ghi một lần.

Input

• Dòng đầu chứa số ~n~ (~n\leq 10^5~).
• Dòng thứ hai chứa n số nguyên dương ~A_1,A_2,\ldots,A_n~ (~A_i\leq 10^6~).

Output

• Gồm ~n~ dòng, mỗi dòng ghi số hạng thứ ~A_i~ và số lần xuất hiện của chúng.

Example

Input

9
2 3 1 2 3 4 5 4 3

Output

1 1
2 2
3 3
4 2
5 1

Levi mở cửa hàng bán quần áo, anh ta có ~1~ đống tất mà cần phải ghép đôi theo màu để bán. Mỗi màu có thể được biểu diễn bởi ~1~ số nguyên dương.

Yêu cầu : Hãy xác định giúp anh ta biết anh ta có thể có tối đa bao nhiêu đôi tất cùng màu.

Input

• Dòng đầu tiên gồm ~1~ số nguyên ~n~ đại diện cho số chiếc tất ~(1~ ~\leq~ ~n~ ~\leq~ ~100).~
• Dòng thứ hai gồm ~n~ số nguyên dương, mỗi số đại diện cho ~1~ màu tất ~(~các số này không lớn hơn ~100)~

Output

• Gồm ~1~ số duy nhất là kết quả của bài toán.

Example

Input

7
1 2 1 2 1 3 2

Output

2

Cho một mảng gồm ~n~ số nguyên dương ~a_1,~ ~a_2,~ ~a_3,~ ~...,~ ~a_n.~

Yêu cầu : Hỏi có bao nhiêu cặp số bằng nhau ? ~(~Bao nhiêu cặp ~a_i~ ~=~ ~a_j~ với ~i~ ~\neq~ ~j,~ ~(ai,~ ~aj)~ và ~(aj,~ ~ai)~ chỉ được tính là ~1~ cặp~).~

Input

• Dòng thứ nhất là chiều dài ~n~ của mảng ~(1~ ~\leq~ ~n~ ~\leq~ ~10^5).~
• Dòng thứ hai gồm ~n~ số nguyên ~a_1,~ ~a_2,~ ~a_3,~ ~...,~ ~a_n~ ~(1~ ~\leq~ ~a_i~ ~\leq~ ~10^5),~ mỗi số cách nhau một khoảng trắng.

Output

• Là số nguyên xác định số lượng các cặp bằng nhau.

Example

Input

5
8 2 9 8 1

Output

1

Input

7
6 2 4 2 4 3 4

Output

4

Một lớp học nọ có ~N~ học sinh. Một ngày đẹp trời, nhận thấy số học sinh đi học chỉ có ~M~ người, ít hơn ~N~ nên quyết định nhờ bạn điểm danh các học sinh trong lớp. Hãy viết một chương trình cho biết số thứ tự của các học sinh vắng mặt theo thứ tự tăng dần.

Biết rằng, lớp học đánh số thứ tự cho học sinh từ ~1~ cho đến ~N~.

Input

• Dòng đầu tiên chứa hai số nguyên dương lần lượt là ~N~ và ~M~ ~(1 \leq M < N \leq 10^5)~
• Dòng thứ hai chứa ~M~ số nguyên khác nhau từng đôi một, có giá trị trong đoạn ~[1, N]~.

Output

• In ra một danh sách các số nguyên, là số thứ tự của những học sinh vắng mặt, theo thứ tự tăng dần.

  Example

Input

5 3
5 2 3 

Output

1 4

Note Trong năm học sinh với số thứ tự ~{1, 2, 3, 4, 5}~ chỉ có học sinh với stt ~{2, 3, 5}~ đi học. Vậy, kết quả là ~{1, 4}~, in ra theo thứ tự tăng dần.

Input

2 1
2 

Output

1

Cho một xâu ký tự ~S~ chỉ gồm các chữ cái thường a..z. Xâu đối xứng là xâu kí tự mà khi viết từ phải qua trái hay từ trái qua phải thì xâu đó không thay đổi. Ví dụ: ~madam~, ~ioi~ là các xâu đối xứng.

Yêu cầu: Với xâu ký tự ~S~ cho trước, hãy tính số ký tự bỏ đi ít nhất để các ký tự còn lại có thể sắp xếp được thành một xâu đối xứng.

Ví dụ:

• Cho xâu aammmda thì cần bỏ 2 ký tự a và m thì xâu còn lại là ammda và xếp lại thành madam là xâu đối xứng.
• Cho xâu aaabbcc thì không cần bỏ ký tự thì xâu đó xếp lại thành bcaaacb là xâu đối xứng.

Input

• Một xâu ký tự ~S~ có ~n~ ký tự (~n \le 10^5~) chỉ gồm các ký tự chữ cái thường a..z.

Output

• Một số nguyên là số lượng ký ít nhất cần bỏ để các ký tự còn lại có thể sắp xếp được thành một xâu đối xứng.

  Scoring

• Subtask ~1~: (~30\%~ số điểm): chỉ chứa 2 ký tự a và b.

• Subtask ~2~: (~30\%~ số điểm): chỉ chứa 3 loại ký tự bất kỳ.
• Subtask ~3~: (~40\%~ số điểm): trường hợp còn lại.

  Example

Input

aammmda

Output

2

Input

aaabbcc

Output

0

Conan đang trong một vụ án cực kì hóc búa, đã có đến 2 vụ án mạng xảy ra. Tại hiện trường 2 vụ án đều để lại dòng chữ kì lạ. Có vẻ như đó chính là gợi ý mà hung thủ để lại. Hung thủ dường như đang cố thách thức vị thám tử lừng danh của chúng ta. Bằng tài năng suy luận tài tình của mình, Conan đã khám phá đã ra được gợi ý của hung thủ chính là sự tương đồng của 2 dòng chữ đó. Tuy nhiên các dòng chữ rất dài, Conan giỏi suy luận nhưng lại không giỏi lập trình. Bạn là một lập trình viên giỏi, bạn hãy giúp Conan nhé.

Yêu cầu: Cho 2 chuỗi kí tự ~a~ và ~b~. Hãy xác định xem chuỗi ~a~ và ~b~ giống nhau bao nhiêu kí tự?

Input

• Dòng thứ nhất là chuỗi kí tự ~a (1 \leq |a| \leq 10^{5})~.
• Dòng thứ hai là chuỗi kí tự ~b~ ~(1 \leq |b| \leq 10^{5})~.
• Các chuỗi chỉ gồm các kí tự từ ~\texttt{a}~ ~\rightarrow~ ~\texttt{z}~, ~|x|~ là số lượng ký tự của chuỗi ~x~.

Output

• Gồm một dòng duy nhất là số lượng kí tự giống nhau.

Example

Input

aaabb
baa

Output

3

Note Cả 2 chuỗi đều có 2 kí tự a và 1 kí tự b. Vậy kết quả in ra 3.

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à ~n ≤ 10^5~. Một cặp số được gọi là cặp tương đồng với ~x~, nếu cặp số này có tổng bằng số ~x~ cho trước nào đó.

Yêu cầu: Hãy đếm xem trong dãy số A có bao nhiêu cặp số ~(A_i; A_j)~ tương đồng với ~x~ (có nghĩa là ~A_i + A_j = x~) với ~i < j~.

Dữ liệu vào:

• Dòng đầu tiên chứa dãy số ~n, x~ (~n ≤ 10^5, x ≤ 10^6~).

• Dòng thứ 2 chứa ~n~ phần tử của dãy số A (~A_i ≤ 10^9~).

Kết quả: Ghi ra một số nguyên là cặp đôi tương đồng của dãy số.

Input:

7 6
1 2 4 3 4 5 3

Output:

4

Một cửa hàng có tất cả các món của cửa hàng này đều đồng giá ~C~ đô.

Nhân dịp cuối tuần cửa hàng có khuyến mãi cho khách hàng cứ mỗi lần đặt ~15~ món thì cửa hàng sẽ trả lại cho bạn ~S~ đô và tính số lượng để khuyến mãi về lại thành ~0~

Tận dụng điều này thaopamt đã đặt ~N~ món để ăn no bụng.

Yêu Cầu: Bạn hãy tính số tiền thaopamt phải trả sau khi đã áp dụng khuyến mãi.

Input

• Chứa ba số nguyên dương lần lượt là ~N,C,S~ ~(1 \le N \le 10^9,1 \le C \le 10^5,1 \le S \le 1000)~, mỗi số cách nhau một khoảng trắng.

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Example

Input

20 800 200

Output

15800

Note thaopamt phải trả ~800 \times 20 = 16000~ đô và trừ phần khuyến mãi của cửa hàng đi ~200~ đô nên thaopamt phải trả ~16000-200=15800~ đô.

Input

30 400 1000

Output

10000

Note thaopamt phải trả ~400 \times 30 = 12000~ đô và trừ phần khuyến mãi của cửa hàng đi ~2000~ đô nên thaopamt phải trả ~12000-2000=10000~ đô.

Có một tháp các ô vuông bằng nhau có hình dạng giống một tam giác cân. Các hàng tính từ trên xuống dưới có số ô vuông lần lượt là ~1; 3; 5; 7; …~. Một tháp ô vuông có ~n~ hàng gọi là tháp ô vuông bậc ~n~ (~n~ là số tự nhiên).

Ví dụ ở hình vẽ sau ta có một tháp ô vuông bậc ~3~:

Yêu cầu: Cho trước một tháp ô vuông bậc ~n~. Hãy tính xem trong tháp ô vuông này có tất cả mấy hình vuông tạo thành từ các ô vuông đó.

Input

• Chứa một số ~n~ (~n \le 5 \times 10^5~).

Output

• Ghi ra số nguyên ~m~ là số các hình vuông cần tìm.

  Example

Input

3

Output

11

Một số tự nhiên được gọi là số yêu thương nếu nó là một số đối xứng, và có số lượng chữ số là số chẵn.

Yêu cầu: Cho số tự nhiên ~n(n \leq 10 ^ {100000})~. Hãy tìm số yêu thương thứ ~n~.

Input

• Số nguyên dương ~n(n \leq 10 ^ {100000})~.

Output

• Số yêu thương thứ ~n~.

Chú ý: Nếu có nhiều kết quả thì chỉ ghi ra số lớn nhất trong các kết quả tìm được.

Example

Input

1 

Output

11

Input

10 

Output

1001

Note

Giải thích: 10 số yêu thương đầu tiên là: ~11, 22, 33, 44, 55, 66, 77, 88, 99, 1001~.

Cho dãy ~A~ gồm ~N~ phần tử số nguyên. Tìm tổng các tích của của mỗi phần tử ~A[i]~ với các phần tử ~A[j]~ với mọi ~j>i~.

Input

• Dòng đầu ghi số ~N (N \le 10^6)~
• Dòng tiếp theo ghi ~N~ số nguyên, các số cách nhau bởi dấu cách ~A[i] \le 10^6~.

Output

• Ghi một số là kết quả của bài toán

Sample Input

4
9 3 4 2

Sample Output

107

Giải thích: Tích = ~(9*3+9*4+9*2)+(3*4+3*2)+(4*2) = 107~

Cho một dãy gồm n số nguyên dương ~a_1, a_2, ..., a_n~. Một hàm ~f~ được định nghĩa như sau: ~f(x) = x * count_a(x)~

với ~count_a(x)~ là số lần xuất hiện của ~x~ có trong dãy ~a~.

Yêu cầu

Hãy tìm phần từ ~a_i~ có ~f(a_i)~ lớn nhất ~(1 \le i \le n)~

Input

• Dòng đầu tiên là số nguyên dương ~n~ ~(n \le 10^5)~,
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(a \le 10^9)~.

Output

• In ra phần từ ~a_i~ có ~f(a_i)~ lớn nhất ~(1 \le i \le n)~. Nếu có nhiều kết quả thỏa mãn, in ra kết quả lớn nhất.

Scoring

• Subtask ~1~ (~80\%~ số điểm): ~n\le 10^3, a_i \le 10^6~.
• Subtask ~2~ (~30\%~ số điểm): không có ràng buộc gì thêm.

Ví dụ

Input

4
1 2 1 1

Output

1

Input

5
1 2 3 4 5

Output

5

Cho 2 dãy số: Dãy A có n phần tử, dãy B có m phần tử. Các phần tử là các số nguyên.

Yêu cầu: Tìm số lượng phần tử của dãy A có mặt trong dãy B.

Dữ liệu vào: trong tập tin văn bản NNUMBER.INP, gồm:

- Dòng đầu ghi 2 số nguyên n,m (0<n,m<5*10⁵).

- Dòng thứ 2 ghi n số nguyên a₁, a₂,…,a_i,...,a_n cho biết giá trị của các phần tử trong dãy A.

- Dòng thứ 3 ghi m số nguyên b₁, b₂,…,b_j,..,b_m cho biết giá trị của các phần tử trong dãy B (|ai|,|bj|≤10⁶).

Kết quả: Ghi vào tập tin văn bản NNUMBER.OUT gồm 1 dòng ghi số lượng tìm được.

Sample input

5 6
2 5 6 8 6
5 5 8 6 1 3

Sample output

4