Cho một mảng gồm ~n~ số nguyên.
Hãy đếm xem mỗi số xuất hiện bao nhiêu lần trong mảng,
và in kết quả theo thứ tự tăng dần của giá trị phần tử.

Input

• Dòng đầu tiên chứa số nguyên ~n~ (1 ≤ ~n~ ≤ 2×10⁵) — số lượng phần tử trong mảng.
• Dòng thứ hai chứa ~n~ số nguyên ~a₁, a₂, …, a~ (~aᵢ~ ≤ 10⁶).

Output

In ra mỗi số khác nhau trong mảng cùng với số lần xuất hiện của nó.

Ví dụ

Input 1

8
1 5 2 1 2 5 2 5

Output 1

1 2
2 3
5 3

Hôm nay là 1 ngày đẹp trời, Kluco vừa học xong cách đếm số, cô giáo hpgiakhang1405 đã cho Kluco 1 bài tập đếm số như sau:

Cô giáo cho Kluco ~n~ số tự nhiên và ~q~ câu hỏi ~(3 \leq n, q \leq 10^6)~. Với mỗi câu hỏi chứa 1 số tự nhiên ~q_i~, Kluco sẽ phải đếm số lượng số lượng phần tử ~q_i~ có trong ~n~ số tự nhiên đã cho.

Vì cô giáo này là ác quỷ, nên số lượng số quá nhiều khiến Kluco choáng váng, nên anh ấy đã nhờ bạn giúp anh ấy hoàn thành bài tập này.

Input

• Dòng đầu tiên số nguyên ~n~ ~(3 \leq n \leq 10^6)~
• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_i~ ~(1 \leq a_i \leq 10^6)~
• Dòng tiếp theo chứa số nguyên ~q~ ~(3 \leq q \leq 10^6)~
• ~q~ dòng tiếp theo chứa các số ~q_i~ ~(1 \leq q_i \leq 10^6)~

Output

• ~q~ dòng là số lượng số ~q_i~ có trong ~n~ số tự nhiên đã cho

Sample Input 1

3
1 1 2
3
1
2
3

Sample Output 1

2
1
0

Hôm nay là 1 ngày đẹp trời, Kluco vừa học xong cách đếm số, cô giáo hpgiakhang1405 đã cho Kluco 1 bài tập đếm số như sau:

Cô giáo cho Kluco ~n~ số tự nhiên và ~q~ câu hỏi. Với mỗi câu hỏi chứa 1 số tự nhiên ~q_i~, Kluco sẽ phải đếm số lượng số lượng phần tử ~q_i~ có trong ~n~ số tự nhiên đã cho.

Vì cô giáo này là ác quỷ, nên số lượng số quá nhiều khiến Kluco choáng váng, nên anh ấy đã nhờ bạn giúp anh ấy hoàn thành bài tập này.

Input

• Dòng đầu tiên số nguyên ~n~ ~(1 \leq n \leq 2 \times 10^5)~.
• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_i~ ~(-10^9 \leq a_i \leq 10^9)~.
• Dòng tiếp theo chứa số nguyên ~q~ ~(1 \leq q \leq 2 \times 10^5)~.
• ~q~ dòng tiếp theo chứa các số ~q_i~ ~(-10^9 \leq q_i \leq 10^9)~.

Output

• ~q~ dòng là số lượng số ~q_i~ có trong ~n~ số tự nhiên đã cho.

Sample Input

3
1 1 2
3
1
2
3

Sample Output

2
1
0

Sau mỗi buổi tập luyện, banmkh62 thường mang đến các chai nước ngọt để làm phần thưởng cho những sinh viên xuất sắc. Mỗi chai nước ngọt được gắn một số nguyên ~a_i~. Sau khi trao thưởng, banmkh62 còn có các chai nước "may mắn" dành cho các sinh viên có cặp số trên hai chai nước bất kỳ, ~a_i~ và ~a_j~ ~(i < j)~, thỏa mãn điều kiện ~a_i + a_j = k~, với ~k~ là một số nguyên cho trước.

Nhiệm vụ của bạn là tìm xem banmkh62 cần phải chuẩn bị bao nhiêu chai nước "may mắn" dựa trên điều kiện này.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~:
  • ~n~ là số lượng chai nước ngọt ~(1 \le n \le 10^3).~
  • ~k~ là giá trị tổng tuyệt đối mà hai số nguyên trên chai nước phải đạt ~(1 \le k \le 10^4)~.
• Dòng thứ hai chứa n số nguyên ~a_1, a_2,...,a_n~ ~(0 \le a_i \le 10^4)~, là các số ghi trên từng chai nước ngọt.

Output

• In ra một số nguyên duy nhất là số lượng cặp số may mắn thỏa mãn điều kiện trên.

Sample Input 1

8 7
6 2 3 1 6 6 6 4

Sample Output 1

5

Sau mỗi buổi tập luyện, banmkh62 thường mang đến các chai nước ngọt để làm phần thưởng cho những sinh viên xuất sắc. Mỗi chai nước ngọt được gắn một số nguyên ~a_i~. Sau khi trao thưởng, banmkh62 còn có các chai nước "may mắn" dành cho các sinh viên có cặp số trên hai chai nước bất kỳ, ~a_i~ và ~a_j~ ~(i < j)~, thỏa mãn điều kiện ~a_i + a_j = k~, với ~k~ là một số nguyên cho trước.

Nhiệm vụ của bạn là tìm xem banmkh62 cần phải chuẩn bị bao nhiêu chai nước "may mắn" dựa trên điều kiện này.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~:
  • ~n~ là số lượng chai nước ngọt ~(1 \le n \le 10^5).~
  • ~k~ là giá trị tổng tuyệt đối mà hai số nguyên trên chai nước phải đạt ~(1 \le k \le 10^6)~.
• Dòng thứ hai chứa n số nguyên ~a_1, a_2,...,a_n~ ~(0 \le a_i \le 10^6)~, là các số ghi trên từng chai nước ngọt.

Output

• In ra một số nguyên duy nhất là số lượng cặp số may mắn thỏa mãn điều kiện trên.

Sample Input 1

8 7
6 2 3 1 6 6 6 4

Sample Output 1

5

Thầy Luna cho đề kiểm tra cho ~n~ SV làm và sau khi chấm thì phát hiện ra nhiều bài bằng điểm nhau. Thực ra đó là chuyện bình thường nhưng thầy lại khá nhạy cảm nên muốn gọi tất cả các cặp SV bằng điểm nhau lên vấn đáp lại xem có copy bài của nhau hay không. Hỏi thầy phải hỏi tất cả bao nhiêu cặp?

Input

Dòng đầu tiên gồm số SV là ~n~, trong đó ~2 \le n \le 10^5.~ Dòng tiếp theo gồm điểm số của các SV, các số này là số tự nhiên có giá trị không quá ~10^6.~

Output

Số cặp SV thầy cần vấn đáp.

Sample input 1

5
1 1 1 2 2

Sample output

4

Giải thích: nếu đánh số các SV là ~1,2,3,4,5~ thì các cặp bị vấn đáp sẽ là: ~(1,2),(2,3),(3,1)~ và ~(4,5).~

Ở một vương quốc nọ vô cùng rộng lớn có diện tích ~N \times M~ hẹt ta nhưng lại được cai trị bởi một vị vua bất tài tên là Kluco, vì sự kém cỏi của mình nên vương quốc thường xuyên bị các thế lực đen tối xâm chiếm và c.ư.ớ.p bóc, để an toàn Kluco đã phân bổ đều các thành phố trên toàn bộ lãnh thổ để giảm thiểu thiệt hại khi bị các thế lực khác xâm lược nên cứ mỗi 1 hẹt ta vuông thì sẽ mọc lên 1 thành phố ở trung tâm.

Vào một ngày nọ ma vương unKluco là một phiên bản Kluco hắc ám tới từ một vũ trụ song song và thấy vô cùng ngứa mắt với cách phân bổ này của Kluco nên unKluco đã tấn công vào vương quốc của Kluco để bóc lột, nếu không đưa đủ vàng thì unKluco sẽ xoá sổ toàn bộ vương quốc.

Ma vương unKluco rất ghét hình vuông nên đã đề nghị cứ mỗi bốn thành phố riêng biệt tạo nên một hình vuông hoàn chỉnh thì unKluco sẽ thu của Kluco ~1~ thỏi vàng. Vì bất tài nên Kluco cũng chả giỏi tính toán, trong lúc không thể tính được số vàng phải trả là bao nhiêu thì Kluco nhớ ra rằng vương quốc mình dẫn còn một lập trình viên tài ba đó chính là bạn.

Bạn hãy giúp Kluco pha này nhé, biết rằng ~1 \leq N,M \leq 1000~

Input

• Hai số nguyên ~N,M (1 \leq N,M \leq 1000)~ , đại diện cho chiều dài và chiều rộng của vương quốc.

Output

• Một số nguyên duy nhất là số thỏi vàng unKluco nhận được.

Sample Input

3 3

Sample Output

6

Ở một vương quốc nọ vô cùng rộng lớn có diện tích ~N \times M~ hẹt ta nhưng lại được cai trị bởi một vị vua bất tài tên là Kluco, vì sự kém cỏi của mình nên vương quốc thường xuyên bị các thế lực đen tối xâm chiếm và c.ư.ớ.p bóc, để an toàn Kluco đã phân bổ đều các thành phố trên toàn bộ lãnh thổ để giảm thiểu thiệt hại khi bị các thế lực khác xâm lược nên cứ mỗi 1 hẹt ta vuông thì sẽ mọc lên 1 thành phố ở trung tâm.

Vào một ngày nọ ma vương unKluco là một phiên bản Kluco hắc ám tới từ một vũ trụ song song và thấy vô cùng ngứa mắt với cách phân bổ này của Kluco nên unKluco đã tấn công vào vương quốc của Kluco để bóc lột, nếu không đưa đủ vàng thì unKluco sẽ xoá sổ toàn bộ vương quốc.

Ma vương unKluco rất ghét hình vuông nên đã đề nghị cứ mỗi bốn thành phố riêng biệt tạo nên một hình vuông hoàn chỉnh thì unKluco sẽ thu của Kluco ~1~ thỏi vàng. Vì bất tài nên Kluco cũng chả giỏi tính toán, trong lúc không thể tính được số vàng phải trả là bao nhiêu thì Kluco nhớ ra rằng vương quốc mình dẫn còn một lập trình viên tài ba đó chính là bạn.

Bạn hãy giúp Kluco pha này nhé, biết rằng ~1 \leq N,M \leq 10^9~

Input

• Gồm Q dòng ~Q (1 \leq Q \leq 1000)~ , đại diện cho ~Q~ truy vấn của ~Q~ vũ trụ khác nhau, lưu ý input không có ~Q~.
• Mỗi dòng có hai số nguyên ~N,M (1 \leq N,M \leq 10^9)~ , đại diện cho chiều dài và chiều rộng của vương quốc.

Output

• Một số nguyên duy nhất là số thỏi vàng unKluco nhận được.

Sample Input

3 3

Sample Output

6

Giới Hạn

• Có 50% số test với ~N, M \leq 10^6~
• Còn lại không có ràng buộc nào