Cho dãy gồm ~n~ số nguyên ~a_1, a_2, \ldots, a_n~. Có ~q~ truy vấn, mỗi truy vấn cho một vị trí ~k~. Với mỗi truy vấn, hãy cho biết:

• có bao nhiêu vị trí ~x < k~ mà ~a_x = a_k~;
• có bao nhiêu vị trí ~y > k~ mà ~a_y = a_k~.

Dữ liệu

• Dòng đầu tiên ghi hai số nguyên dương ~n~ và ~q~ (~1 \le n, q \le 10^6~): độ dài dãy và số truy vấn.
• Dòng thứ hai ghi ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~0 \le a_i \le 10^9~).
• ~q~ dòng tiếp theo, dòng thứ ~i~ ghi một số nguyên dương ~k_i~ (~1 \le k_i \le n~) là truy vấn thứ ~i~.

Kết quả

• Gồm ~q~ dòng; dòng thứ ~i~ ghi hai số nguyên: số vị trí ~x~ và số vị trí ~y~ tương ứng với truy vấn thứ ~i~.

Ví dụ

CNTNUM.INP

10 4
2 1 3 2 2 5 4 2 3 5
1
7
4
10

CNTNUM.OUT

0 3
0 0
1 2
1 0

Giải thích: Với ~k = 1~, giá trị là 2; không có vị trí nào trước nó, còn sau nó có ba vị trí chứa 2 (vị trí 4, 5, 8). Với ~k = 7~, giá trị 4 chỉ xuất hiện một lần nên cả hai số đều là 0. Các truy vấn còn lại tính tương tự.

Giới hạn

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