Cho số nguyên \(n\) và dãy số nguyên \(a_1,a_2,…,a_n. \)

Yêu cầu: Có \(q\) truy vấn, mỗi truy vấn có dạng là một số \(k\). Cho biết có bao nhiêu số trước vị trí \(k\) mà có giá trị bằng \(a_k\) và có bao nhiêu số sau vị trí \(k\) mà có giá trị bằng \(a_k\).

Input

• Dòng thứ nhất chứa hai số nguyên \(n,q (1≤n,q≤10^6 ).\)

• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,…,a_n (0≤a_i≤10^9 ).\)

• Dòng thứ \(i\) trong \(q\) dòng tiếp theo, chứa một số nguyên \(k_i (1≤k_i≤n),\) biểu diễn truy vấn thứ \(i\).

Output

• Ghi trên \(q\) dòng, dòng thứ \(i\) ghi 2 số nguyên \(r1\) và \(r2\) là kết quả tìm được của truy vấn thứ \(i\).

Ràng buộc

• Subtask 1: \(n,q≤10^3.\)

• Subtask 2: \(a_i≤10^6\)

• Subtask 3: \(n,q≤10^6,a_i≤10^9.\)

Sample Input

10 3
6 2 4 6 4 2 6 4 2 3 
1 
6
4

Sample Output

0 2
1 1
1 1